堆的定義
堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，可以形象化的看成一顆完全二叉樹萝映，一般內(nèi)部的存儲結(jié)構(gòu)為數(shù)組吴叶；堆中的某個節(jié)點(diǎn)總是不大于或者（不小于）其左右節(jié)點(diǎn)，其中前者為成為小頂堆（最小堆序臂，堆頂為最小值）蚌卤，后者成為大頂堆（最大堆，堆頂為最大值）
堆的一些操作
- build: 建立一個堆
- insert: 往堆中插入一個新節(jié)點(diǎn)
- update: 更新某個節(jié)點(diǎn)的值, 根據(jù)節(jié)點(diǎn)的新值重新調(diào)整堆奥秆，使其符合堆的特性
- get_top : 獲取堆頂?shù)墓?jié)點(diǎn)
- delete_top : 刪除堆頂?shù)墓?jié)點(diǎn), 然后重新調(diào)整堆逊彭，使其滿足堆的特性
下面以最大堆為例進(jìn)行堆操作的說明
- 建堆
-
自上到下構(gòu)建堆
- 自上到下構(gòu)建堆的流程是：假定數(shù)組arr的前i個節(jié)點(diǎn)已經(jīng)滿足堆的特性，然后新增一個節(jié)點(diǎn)arr[i]到數(shù)組尾,調(diào)整堆使得數(shù)組arr[0~i]滿足堆的特性构订；當(dāng)i = n -1（n是數(shù)組長度）時侮叮，則建堆完畢；
- 新增節(jié)點(diǎn)arr[i]到數(shù)組尾悼瘾，調(diào)整的過程：可以形象的描述為囊榜，該節(jié)點(diǎn)沿著到根節(jié)點(diǎn)的二叉樹路徑，進(jìn)行上负ニ蕖卸勺；如果該節(jié)點(diǎn)比其父節(jié)點(diǎn)大，則將該節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換烫扼，然后將當(dāng)前節(jié)點(diǎn)設(shè)置為其父節(jié)點(diǎn)繼續(xù)進(jìn)行上浮比較曙求；如果該節(jié)點(diǎn)比其父節(jié)點(diǎn)小，則停止上覆闹搿圆到；直到該節(jié)點(diǎn)上浮到根節(jié)點(diǎn)，則本次上浮調(diào)整結(jié)束
- 代碼示例
struct max_heap_t { int32_t* arr; int32_t n; max_heap_t (int32_t* input_arr, int32_t arr_size){ arr = new int32_t[arr_size]; memcpy(arr, input_arr, sizeof(int32_t) * arr_size); n = arr_size; } ~max_heap_t () { if (arr) { delete[] arr; arr = nullptr; } } /** time complexity => O(nlogn) */ void build_heap_from_top_to_bottom() { for (int32_t i = 1; i < n; i++) { heap_ajust_from_bottom_to_top(i); } } /* O(logn) */ void heap_ajust_from_bottom_to_top(int32_t bottom_index) { int32_t tmp = arr[bottom_index]; while (bottom_index > 0) { int32_t parent_index = (bottom_index - 1) / 2; if (arr[parent_index] < tmp ) { arr[bottom_index] = arr[parent_index]; bottom_index = parent_index; } else { break; } } arr[bottom_index] = tmp; } - 時間復(fù)雜度
每次上浮調(diào)整的時間復(fù)雜度為O(logn), 總共要調(diào)整n-1次卑吭，所以建堆的時間復(fù)雜度為 O(nlogn)
-
自下到上構(gòu)建堆
- 自下到上構(gòu)建堆的流程是： 從最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)開始一直到到根節(jié)點(diǎn)芽淡，逐步進(jìn)行以選中節(jié)點(diǎn)為起點(diǎn)，進(jìn)行下沉調(diào)整豆赏；到根節(jié)點(diǎn)下沉調(diào)整結(jié)束挣菲，則建堆完畢
- 下沉調(diào)整的過程，可以描述為：從當(dāng)前節(jié)點(diǎn)以及其左右子節(jié)點(diǎn)中選出最大的一個節(jié)點(diǎn)掷邦，如果最大節(jié)點(diǎn)是該節(jié)點(diǎn)本身白胀，則下沉調(diào)整結(jié)束；如果是其左子節(jié)點(diǎn)（或者右子節(jié)點(diǎn)）抚岗，則將該節(jié)點(diǎn)與其左子節(jié)點(diǎn)（或者其右子節(jié)點(diǎn)）交換或杠，然后將當(dāng)前節(jié)點(diǎn)設(shè)置為其左子節(jié)點(diǎn)（后后者右子節(jié)點(diǎn)）繼續(xù)下浮比較；
- 代碼示例
/* O(n) */ void build_heap_from_bottom_to_top() { int32_t max_index = n - 1; for (int32_t i = (max_index - 1) / 2; i >= 0; i--) { heap_adjust_from_top_to_bottom(i, max_index); } } /* O(logn) */ void heap_adjust_from_top_to_bottom(int32_t top_index, int32_t bottom_index) { int32_t tmp = arr[top_index]; while (top_index <= (bottom_index - 1) / 2) { int32_t max_one = tmp; int32_t child_idx = 0; int32_t left_child_idx = top_index * 2 + 1; int32_t right_child_idx = top_index * 2 + 2; if (left_child_idx <= bottom_index && max_one < arr[left_child_idx] ) { max_one = arr[left_child_idx]; child_idx = left_child_idx; } if (right_child_idx <= bottom_index && max_one < arr[right_child_idx] ) { max_one = arr[right_child_idx]; child_idx = right_child_idx; } if (max_one != tmp) { arr[top_index] = max_one; top_index = child_idx; } else { break; } } arr[top_index] = tmp; } - 時間復(fù)雜度
自下到上建堆的時間復(fù)雜度是O(n)
證明方法如下：假定節(jié)點(diǎn)個數(shù)為n宣蔚， 葉子高度為h = log2(n)
1. 假設(shè)根節(jié)點(diǎn)的高度為0向抢，葉子節(jié)點(diǎn)高度為h认境，那么每層包含的元素個數(shù)為2^x，x從0到h挟鸠。
2. 構(gòu)建堆的過程是自下而上叉信，對于每層非葉子節(jié)點(diǎn)需要調(diào)整的次數(shù)為h-x，因此很明顯根節(jié)點(diǎn)需要調(diào)整(h- 0)次艘希，第一層節(jié)點(diǎn)需要調(diào)整(h-1)次硼身，最下層非葉子節(jié)點(diǎn)需要調(diào)整1次。
3. 因此可知覆享，構(gòu)造樹高為h的二叉堆精確時間復(fù)雜度為：
s = 12^(h-1) + 22(h-2)+……+h*20
可以看出以上公式是等差數(shù)列和等比數(shù)列乘積之和佳遂，可以通過錯位相減求：
2s = 2^h + 22^(h-1)+32(h-2)+……+h*21
因此可得:
s = 2s -s = 2^h + 2^(h-1) + 2^(h-2) +…… + 2^1 - h
最終可以通過等比數(shù)列公式進(jìn)行計算得到s = 2*2^h - 2 -h
將代入的s = 2n - 2 - log2(n)，近似的時間復(fù)雜度就是O(n)
轉(zhuǎn)載自: https://blog.csdn.net/hupenghui1224/article/details/57427045
-
堆排序
堆排序的話淹真，無需額外的空間讶迁，直接可以在原堆內(nèi)數(shù)組上進(jìn)行堆排序；
- 堆排序的過程: 對于給定的數(shù)組arr以及長度n核蘸，首先根據(jù)該數(shù)組巍糯，構(gòu)建堆；然后依次將當(dāng)前數(shù)組尾元素arr[i]( i => n -> 0)與堆頂元素交換客扎，然后重新調(diào)整堆(從 arr[0] ~ arr[i - 1])祟峦；一直到當(dāng)前i = 0, 則排序完成；
- 代碼實(shí)例:
void sort() { // build heap first build_heap_from_bottom_to_top(); // sort int32_t tmp = 0; for (int32_t i = n - 1; i > 0;) { // move heap top to end tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; // adjust the heap heap_adjust_from_top_to_bottom(0, --i); } }
TopK問題
TopK問題描述：在N個無序元素中徙鱼，找到最大的K個（或最小的K）
按照一般排序算法來尋找的話宅楞，時間復(fù)雜度為O(nlogn) + O(k); 當(dāng)N很大，而K很小的時候袱吆，這種方法很慢厌衙；
可以采用堆來解決這個問題；下面以找到最大的K個值為例
算法流程：取該數(shù)組的前K個元素绞绒，構(gòu)建一個最小堆婶希；然后從該無序數(shù)組的第k個元素開始，一直到數(shù)組尾蓬衡，遍歷該數(shù)組喻杈，將當(dāng)前元素與最小堆的堆頂元素比較，如果當(dāng)前元素大于堆頂元素（最大的K個值里面的最小的那個）狰晚，那么可以認(rèn)為當(dāng)前元素可能是要尋找的最大的K個元素之一筒饰，則將當(dāng)前元素替換堆頂，然后重新進(jìn)行堆調(diào)整壁晒；當(dāng)遍歷結(jié)束的時候瓷们，最小堆中的K個元素就是要尋找的最大的K個元素
-
代碼示例
void top_k(int32_t* input_arr, int32_t n, int32_t k) { printf("input array: (%d)\n", n); for (int32_t i = 0; i < n; ++i) { printf(", %d", input_arr[i]); } printf("\n"); // O(k) // we suppose the k element of the min heap if the default top k element min_heap_t min_heap(input_arr, k); min_heap.build_heap_from_bottom_to_top(); for (int32_t i = k; i < n; ++i) { // compare each element with the min element of the min heap // if the element > the min element of the min heap // we think may be the element is one of what we wanna to find in the top k if (input_arr[i] > min_heap.arr[0]){ // swap min_heap.arr[0] = input_arr[i]; // heap adjust min_heap.heap_adjust_from_top_to_bottom(0, k - 1); } } printf("top k: (%d)\n", k); min_heap.print_arr(); } 算法復(fù)雜度
創(chuàng)建初始堆的過程O(KlogK), 每次堆調(diào)整的時間復(fù)雜度O(logK), 尋找最大K個值的過程(N-K) * O(logK) = O((N-K)logK), 總得時間復(fù)雜度O(NlogK)
