堆的概念

• 堆是一顆完全二叉樹
• 每個(gè)結(jié)點(diǎn)的值都小于子結(jié)點(diǎn)的值，這顆二叉樹為小根堆
• 每個(gè)結(jié)點(diǎn)的值都大于子結(jié)點(diǎn)的值，這顆二叉樹為大根堆
• 堆的定義如下：n個(gè)元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆。
  
  堆的性質(zhì)
• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
• 堆總是一棵完全二叉樹。

堆的實(shí)現(xiàn)

在講堆的實(shí)現(xiàn)前，我們首先要知道堆需要實(shí)現(xiàn)的功能。

• HeapPush
• HeapPop(刪除根結(jié)點(diǎn))
• HeapTop
• HeapSize
• HeapEmpty
  接下來(lái)我們要先創(chuàng)建和銷毀一個(gè)堆。

typedef int HeapType;
typedef struct Heap
{HeapType* arr;int size;int capacity;
}Hp;
void HeapInit(Hp* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}
void HeapDestroy(Hp* php)
{assert(php);free(php->arr);php->arr = NULL;php->capacity = php->size = 0;
}

HeapPush

實(shí)現(xiàn)HeapPush時(shí)難點(diǎn)在于如何保持整體是一個(gè)堆。
即在一個(gè)堆的后面插入一個(gè)值，那么這棵完全二叉樹大概率不會(huì)是堆，那么我們需要將這個(gè)值和其父結(jié)點(diǎn)比較，再根據(jù)需要交換值，也就是AdjustUp。
那么接下來(lái)以小根堆為例，實(shí)現(xiàn)HeapPush。

void Swap(HeapType* a, HeapType* b)
{HeapType tmp = *a;*a = *b;*b = tmp;
}
void AdjustUp(HeapType* arr, int child)
{int parent = (child - 1) / 2;while (child>0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
void HeapPush(Hp* php, HeapType x)
{assert(php);if (php->size == php->capacity){int newcapacity = (php->capacity == 0 ? 4 : 2 * php->capacity);HeapType * tmp = (HeapType*)realloc(php->arr,newcapacity * sizeof(HeapType));if (!tmp){perror("realloc fail!");exit(-1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;php->size++;AdjustUp(php->arr, php->size - 1);
}

HeapPop

實(shí)現(xiàn)HeapPop也是和HeapPush一樣，需要考慮的是如何維持整體完全二叉樹是一個(gè)堆，由于我們刪除的是根結(jié)點(diǎn)，如果將根結(jié)點(diǎn)的子結(jié)點(diǎn)向上調(diào)整，那么整體二叉樹就會(huì)空出一個(gè)位置，導(dǎo)致變成非完全二叉樹。
這里的解決辦法是將根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)交換，刪除最后一個(gè)結(jié)點(diǎn)，然后再對(duì)根結(jié)點(diǎn)進(jìn)行向下調(diào)整。

void AdjustDown(HeapType* a, int n, int parent)
{int child = 2 * parent + 1;while (child<n){if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent - 1;}else{break;}}
}
void HeapPop(Hp* php)
{assert(php);assert(php->size);Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;AdjustDown(php->arr, php->size, 0);
}

HeapTop HeapSize HeapEmpty

實(shí)現(xiàn)了Heap的Push和Pop后，那么取根結(jié)點(diǎn)的值和判空、判滿也是手到擒來(lái)的。

HeapType HeapTop(Hp* php)
{assert(php);assert(php->size);return php->arr[0];
}
size_t HeapSize(Hp* php)
{assert(php);return php->size;
}
bool HeapEmpty(Hp* php)
{assert(php);return php->size == 0;
}

堆的應(yīng)用

實(shí)現(xiàn)了堆那么我們肯定要知道能用在什么地方才行，實(shí)際上堆的應(yīng)用也是非常廣泛的：

1. 實(shí)現(xiàn)堆排序
2. 求Top K值問(wèn)題
3. 求中位數(shù)、百分位數(shù)

等等。
堆的應(yīng)用還有很多，這里就不一一贅述了。