算法 之 堆 - 小结

之前我们讨论的堆，都把最大键值存储在根节点中，这种类型的堆可以看作是最大堆。

我们还可以创建另一种堆，把最键小值存储在根节点中，根节点以外的节点的键值，大于或等于存储在它父节点中的键值，这种类型的堆可以看作是最小堆。

具体是用最大堆还是最小堆，就根据我们自身的需要来选择了。

?

堆的算法到这里就讲完了，下面这段代码包括了之前讲过的堆的所有算法：

#include <stdio.h>#include <stdlib.h>void siftUp(int* heap, int index);void siftDown(int* heap, int index);void siftDown(int* heap, int siftDownTo, int index);int* insertElement(int* heap, int element);int* deleteElement(int* heap, int index);int* makeHeap(int* array, int arrayLength);void heapSort(int* heap);void print(char* description, int* heap);void siftUp(int* heap, int index){int heapLength = heap[0];if (index < 1 || index > heapLength)return;bool done = false;while(!done && index > 1){if (heap[index] > heap[index / 2]){int temp = heap[index];heap[index] = heap[index / 2];heap[index / 2] = temp;}else{done = true;}index /= 2;}}void siftDown(int* heap, int index){int heapLength = heap[0];siftDown(heap, heapLength, index);}void siftDown(int* heap, int siftDownTo, int index){if (index < 1 || index * 2 > siftDownTo)return;bool done = false;while(!done && index * 2 <= siftDownTo){index *= 2;if (index + 1 <= siftDownTo && heap[index + 1] > heap[index])index += 1;if (heap[index] > heap[index / 2]){int temp = heap[index];heap[index] = heap[index / 2];heap[index / 2] = temp;}else{done = true;}}}int* insertElement(int* heap, int element){int heapLength = heap[0];int resultHeapLength = heapLength + 1;// 创建一个长度为resultHeapLength+1的int数组int* resultHeap = (int*)malloc(sizeof(heap) * (resultHeapLength + 1));if (resultHeap == NULL)return NULL;resultHeap[0] = resultHeapLength;for (int i = 1; i <= heapLength; i++){resultHeap[i] = heap[i];}resultHeap[resultHeapLength] = element;siftUp(resultHeap, resultHeapLength);return resultHeap;}int* deleteElement(int* heap, int index){int heapLength = heap[0];if (index < 1 || index > heapLength)return heap;int x = heap[index];int y = heap[heapLength];int resultHeapLength = heapLength - 1;// 创建一个长度为resultHeapLength+1的int数组int* resultHeap = (int*)malloc(sizeof(heap) * (resultHeapLength + 1));if (resultHeap == NULL)return NULL;resultHeap[0] = resultHeapLength;for (int i = 1; i <= resultHeapLength; i++){resultHeap[i] = heap[i];}if (index == resultHeapLength)return resultHeap;resultHeap[index] = y;if (y > x){siftUp(resultHeap, index);}else{siftDown(resultHeap, index);}return resultHeap;}int* makeHeap(int* array, int arrayLength){if (array == NULL || arrayLength <= 0)return NULL;int heapLength = arrayLength;int* heap = (int*)malloc(sizeof(array) * (heapLength + 1));if (heap == NULL)return NULL;// heap[0]用来存储数组中堆数据的长度，堆数据heap[1]...heap[heapLength]  // 所以数组的实际长度是heapLength+1，我们只对从数组索引为1开始的heapLength个数据进行操作heap[0] = heapLength;for (int i = 0; i < arrayLength; i++){heap[i + 1] = array[i];}for (int i = heapLength / 2; i >= 1; i--){siftDown(heap, i);}return heap;}void heapSort(int* heap){if (heap == NULL)return;int heapLength = heap[0];int temp = 0;for (int i = heapLength; i >= 2; i--){temp = heap[1];heap[1] = heap[i];heap[i] = temp;siftDown(heap, i - 1, 1);}}void print(char* description, int* heap){printf("%s:\t", description);int heapLength = heap[0];for(int i = 1; i <= heapLength; i++){printf("%d ", heap[i]);}printf("\n");}void main(){const int ARRAY_LENGTH = 10;int array[ARRAY_LENGTH] = { 4, 3, 8, 10, 11, 13, 7, 30, 17, 26 };int* heap = makeHeap(array, ARRAY_LENGTH);print("从数组初始化堆", heap);int* heapAfterInsert = insertElement(heap, 20);print("插入新数据20", heapAfterInsert);free(heap);int* heapAfterDelete = deleteElement(heapAfterInsert, 2);print("删除第2个数据", heapAfterDelete);free(heapAfterInsert);heapSort(heapAfterDelete);print("按非降序排序", heapAfterDelete);free(heapAfterDelete);getchar();}

?

更多内容请参考：

算法 之 堆 - 简介

算法 之 堆 - Sift-up和Sift-down

算法 之 堆 - 插入和删除

算法 之 堆 - 创建堆

算法 之 堆 - 排序