堆的定义
堆是一种特殊的数据结构，可以形象化的看成一颗完全二叉树，一般内部的存储结构为数组；堆中的某个节点总是不大于或者（不小于）其左右节点，其中前者为成为小顶堆（最小堆，堆顶为最小值），后者成为大顶堆（最大堆，堆顶为最大值）
堆的一些操作
- build: 建立一个堆
- insert: 往堆中插入一个新节点
- update: 更新某个节点的值, 根据节点的新值重新调整堆，使其符合堆的特性
- get_top : 获取堆顶的节点
- delete_top : 删除堆顶的节点, 然后重新调整堆，使其满足堆的特性
下面以最大堆为例进行堆操作的说明
- 建堆
-
自上到下构建堆
- 自上到下构建堆的流程是：假定数组arr的前i个节点已经满足堆的特性，然后新增一个节点arr[i]到数组尾,调整堆使得数组arr[0~i]满足堆的特性；当i = n -1（n是数组长度）时，则建堆完毕；
- 新增节点arr[i]到数组尾，调整的过程：可以形象的描述为，该节点沿着到根节点的二叉树路径，进行上浮；如果该节点比其父节点大，则将该节点和父节点进行交换，然后将当前节点设置为其父节点继续进行上浮比较；如果该节点比其父节点小，则停止上浮；直到该节点上浮到根节点，则本次上浮调整结束
- 代码示例
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; } - 时间复杂度
每次上浮调整的时间复杂度为O(logn), 总共要调整n-1次，所以建堆的时间复杂度为 O(nlogn)
-
自下到上构建堆
- 自下到上构建堆的流程是： 从最后一个节点的父节点开始一直到到根节点，逐步进行以选中节点为起点，进行下沉调整；到根节点下沉调整结束，则建堆完毕
- 下沉调整的过程，可以描述为：从当前节点以及其左右子节点中选出最大的一个节点，如果最大节点是该节点本身，则下沉调整结束；如果是其左子节点（或者右子节点），则将该节点与其左子节点（或者其右子节点）交换，然后将当前节点设置为其左子节点（后后者右子节点）继续下浮比较；
- 代码示例
/* 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; } - 时间复杂度
自下到上建堆的时间复杂度是O(n)
证明方法如下：假定节点个数为n， 叶子高度为h = log2(n)
1. 假设根节点的高度为0，叶子节点高度为h，那么每层包含的元素个数为2^x，x从0到h。
2. 构建堆的过程是自下而上，对于每层非叶子节点需要调整的次数为h-x，因此很明显根节点需要调整(h- 0)次，第一层节点需要调整(h-1)次，最下层非叶子节点需要调整1次。
3. 因此可知，构造树高为h的二叉堆精确时间复杂度为：
s = 12^(h-1) + 22(h-2)+……+h*20
可以看出以上公式是等差数列和等比数列乘积之和，可以通过错位相减求：
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
最终可以通过等比数列公式进行计算得到s = 2*2^h - 2 -h
将代入的s = 2n - 2 - log2(n)，近似的时间复杂度就是O(n)
转载自: https://blog.csdn.net/hupenghui1224/article/details/57427045
-
堆排序
堆排序的话，无需额外的空间，直接可以在原堆内数组上进行堆排序；
- 堆排序的过程: 对于给定的数组arr以及长度n，首先根据该数组，构建堆；然后依次将当前数组尾元素arr[i]( i => n -> 0)与堆顶元素交换，然后重新调整堆(从 arr[0] ~ arr[i - 1])；一直到当前i = 0, 则排序完成；
- 代码实例:
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）
按照一般排序算法来寻找的话，时间复杂度为O(nlogn) + O(k); 当N很大，而K很小的时候，这种方法很慢；
可以采用堆来解决这个问题；下面以找到最大的K个值为例
算法流程：取该数组的前K个元素，构建一个最小堆；然后从该无序数组的第k个元素开始，一直到数组尾，遍历该数组，将当前元素与最小堆的堆顶元素比较，如果当前元素大于堆顶元素（最大的K个值里面的最小的那个），那么可以认为当前元素可能是要寻找的最大的K个元素之一，则将当前元素替换堆顶，然后重新进行堆调整；当遍历结束的时候，最小堆中的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(); } 算法复杂度
创建初始堆的过程O(KlogK), 每次堆调整的时间复杂度O(logK), 寻找最大K个值的过程(N-K) * O(logK) = O((N-K)logK), 总得时间复杂度O(NlogK)
