1.堆的概念

如果有一個關鍵碼的集合 K = { k1 ，k2 ，k3 ，…，kn }，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數組中，并且 k(i)?< k(i*2+1) 和?k(i)?< k(i*2+2)， i = 0 ， 1 ， 2…，則稱為小堆 ( 或大堆 ) 。將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。

1.1堆的性質?

堆中某個節點的值總是不大于或不小于其父節點的值；

堆總是一棵完全二叉樹。

1.2堆的存儲結構

?

2.堆的實現

? 堆的構建

?堆的銷毀

?堆的插入

? 堆的刪除

? 取堆頂的數據

? 堆的數據個數

? 堆的判空

2.1堆的構造與銷毀

?

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

?2.2堆的向上與向下調整

void swap(DataType*str1, DataType*str2)
{DataType temp = *str1;*str1 = *str2;*str2 = temp;
}
//向上調整(前提是上面是一個堆)
void AdjustUp(DataType* a, int child)
{//利用孩子找父親,并且比較int parent = (child - 1) / 2;while (child > 0){// "<" 和 ">"取決與建立大小堆if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//向下調整(前提是下面左右子樹是一個堆)
void AdjustDown(int* a, int n, int parent)//n是數量
{//利用父親找兒子并比較大小int child = parent * 2 + 1;while (child < n){//child + 1 < n可能沒有右孩子，防止越界風險if (child + 1 < n && a[child + 1] < a[child]){child++;}// "<" 和 ">"取決與建立大小堆if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;int child = parent * 2 + 1;}elsebreak;}
}

2.3?堆的插入與堆的刪除

//先插入一個數到數組的尾上，再進行向上調整算法，直到滿足堆
void HeapPush(HP* php, DataType x)
{assert(php);//判斷是否要擴容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;DataType* temp = (DataType*)realloc(php->a, newCapacity * sizeof(DataType));if (temp == NULL){perror("realloc fail");return;}php->a = temp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
//刪除堆是刪除堆頂的數據，將堆頂的數據根最后一個數據一換，然后刪除數組
//最后一個數據，再進行向下調整算法。
void HeapPop(HP* php)
{assert(php);swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

2.4堆的數據個數與堆的判空和取得堆的堆頂元素

DataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}