堆的數據結構

對于堆, 有最大堆和最小堆, 在定義一個堆的時候用一個數組表示堆, 同時為了方便定義堆的大小, 用一個 size 表示堆的有效元素, 同時為了區別最大堆和最小堆, 我們用一個函數指針表示這個堆是最大堆還是最小堆.

typedef int (*Compare)(HeapType parent, HeapType child); typedef struct Heap { HeapType data[HeapMaxSize]; int size; Compare cmp; 
} Heap; 

堆的初始化

int Greater(HeapType parent, HeapType child)
{return parent > child? 1 : 0;
}
int Less(HeapType parent, HeapType child)
{return parent < child ? 1 : 0;
}
void HeapInit(Heap* heap, Compare cmp)
{if(heap == NULL){return;}heap -> size = 0;heap -> cmp = cmp;
}

堆的插入

先將要插入得到元素插入到堆對應的數組的最后一個位置, 然后判斷插入結點的值和它的父節點是否符合堆的特征(最大堆:根節點大于它的左孩子和有孩子, 最小堆根節點小于它的左孩子和有孩子), 此時如果插入結點和它的父節點符合堆的特性就直接退出, 如果根節點和父節點不符合堆的特性, 此時就需要將插入結點和它的根節點進行交換, 直到符合堆的特性為止

void HeapInsert(Heap* heap, HeapType value)
{if(heap == NULL){return;//非法輸入}if(heap -> size >= HeapMaxSize){return;}//先將 value 插入到末尾heap -> data[heap -> size++] = value;//判斷父節點和 value 是否符合規定int child = heap -> size - 1;int parent = (child - 1) / 2;while(child > 0){//如果不符合, 就直接將插入的結點和它的父節點進行交換if(heap -> cmp(heap -> data[parent], heap -> data[child]) == 0){Swap(&heap -> data[parent], &heap -> data[child]);child = parent;parent = (child -1) / 2;}//如果符合, 就退出else{break;}}
}

取堆頂元素

直接返回堆對用的數組的第一個元素

int HeapRoot(Heap* heap, HeapType* value)
{if(heap == NULL || value == NULL){return 0;}*value = heap -> data[0];return 1;
}

刪除堆

先將堆的最后一個元素和堆的第一個結點進行交換, 將堆的大小減1, 此時由于交換了兩個元素, 因此可能會破壞堆的結構.先判斷父節點是否有右孩子, 如果有右孩子, 就將左右孩子中比較滿足多結構的一個標記下來, 接著判斷父節點和左右孩子較滿足堆結構的的結點是否需要交換, 如果需要交換就將兩個交換, 否則就直接退出

void HeapErase(Heap* heap)
{if(heap == NULL){return;}if(heap -> size == 0){return;}//將對頂元素和最后一個元素進行交換Swap(&heap -> data[0], &heap -> data[heap -> size - 1]);--heap -> size;int parent = 0;int child = 2 * parent + 1;while(parent >= 0 && parent < heap -> size && child >= 0 && child < heap -> size){//判斷是否有右子樹if(child + 1 < heap -> size){//判斷出左右孩子中較滿足對特性的一個元素if(heap -> cmp(heap -> data[child], heap -> data[child + 1]) == 0){child = child + 1;}//判斷是否需要下沉if(heap -> cmp(heap -> data[parent], heap -> data[child]) == 0){Swap(&heap -> data[parent], &heap -> data[child]);parent = child;child = 2 * parent + 1;}else if(heap -> cmp(heap -> data[parent], heap -> data[child]) == 1){return;}}else{return;}}
}

堆的判空

判斷堆所對應的的數組元素的個數是否為空, 如果為空就返回1, 否則就返回0

 int HeapEmpty(Heap* heap)
{if(heap == NULL){return 1;}if(heap -> size == 0){return 1;}return 0;
}

判斷堆的元素的個數

int HeapSize(Heap* heap)
{if(heap == NULL){return 0;}return heap -> size;
}

堆的銷毀

void HeapDestroy(Heap* heap)
{if(heap == NULL){return;}heap -> size = 0;heap -> cmp = NULL;
}

堆排序

給定一個數組, 將這個數組按照對應的規則進行排序. 即先定義一個堆, 再將數組中的所有元素插入到堆中, 將堆中的元素刪除, 最后恢復對的有效元素, 將堆中的內容全部拷貝到數組中

void HeapSort(HeapType array[], int size, Compare cmp)
{if(array == NULL || size == 0){return;}Heap heap;HeapInit(&heap, cmp);//先將數組中的元素插入到堆中int i = 0;for(; i < size; i++){HeapInsert(&heap, array[i]);}//刪除對中的所有元素for(i = 0; i < size; i++){HeapErase(&heap);}heap.size = size;for(i = 0; i < size; i++){array[i] = heap.data[i];}
}