什么堆？

堆就是用数组实现的完全二叉树结构（除叶节点以外，所有节点都是非空，且叶节点从左到右排列）。完全二叉树中如果每颗子树的的最大值都在顶部就是大根堆。完全二叉树中如果每颗子树的的最小值都在顶部就是小根堆。堆结构就是heapInsert与heapfy操作。堆结构的增加和减少。优先级队列就是堆结构。

堆的heapInsert与heapfy操作

数组：1 9 4 8 2 6

索引：0 1 2 3 4 5

对应的完全二叉树结构：

数组模拟完全二叉树

索引 i：i的左孩子对应的索引2*i+1

i的右孩子对应的索引2*i+2

i的父节点对应的索引(i-1)/2

heapInsert操作

某个位置处在index位置上往上继续移动，自下而上，构建大根堆/小根堆---------heapinsert操作

#include<iostream> #include<vector> using namespace std; //堆操作--------heapinsert 和 heapfy //某个位置处在index位置上 往上继续移动---------heapinsert操作 void heapinsert(vector<int>&arr, int index) { int parent = (index - 1) / 2; while (arr[index] > arr[parent]) { swap(arr[index], arr[parent]); index = parent; parent = (index - 1) / 2; } } int main() { vector<int>arr = { 1,9,4,8,2,6 }; for (int i = 0; i < arr.size(); i++) { heapinsert(arr, i); } for (auto e : arr) { cout << e << " "; } return 0; }

运行结果：

heapfy操作

某个数在index位置，能否往下移动，自上而下，构建大根堆/小根堆---------heapfy操作

#include<iostream> #include<vector> using namespace std; //某个数在index位置，能否往下移动---------heapfy操作 void heapify(vector<int>&arr, int index, int heapsize) { //左孩子下标 int left = 2 * index + 1; //两个孩子中谁大，就把下标给largest while (left < heapsize) //左孩子存在 { int largest; if ((left + 1 < heapsize) && arr[left + 1] > arr[left]) { largest = left + 1; } else { largest = left; } if (arr[largest] > arr[index]) { largest = largest; } else { largest = index; } if (largest == index) { break; } swap(arr[largest], arr[index]); index = largest; left = index * 2 + 1; } } int main() { vector<int>arr = { 1,9,4,8,2,6 }; for (int i = arr.size()-1; i >= 0; i--) { heapify(arr, i, arr.size()); } int len = arr.size(); for (auto e : arr) { cout << e << " "; } return 0; }

运行结果：

堆排序

基本思想

用数组来模拟构建大根堆，完成数组的升序或降序。

堆排序算法代码

（1）升序----构建大根堆

#include<iostream> #include<vector> using namespace std; //堆操作--------heapinsert 和 heapfy //某个位置处在index位置上 往上继续移动---------heapinsert操作 void heapinsert(vector<int>&arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr[index], arr[(index - 1) / 2]); } } //某个数在index位置，能否往下移动---------heapfy操作 void heapify(vector<int>&arr, int index, int heapsize) { //左孩子下标 int left = 2 * index + 1; //两个孩子中谁大，就把下表给largest while (left < heapsize) //左孩子存在 { int largest; if ((left + 1 < heapsize) && arr[left + 1] > arr[left]) { largest = left + 1; } else { largest = left; } if (arr[largest] > arr[index]) { largest = largest; } else { largest = index; } if (largest == index) { break; } swap(arr[largest], arr[index]); index = largest; left = index * 2 + 1; } } //堆排序----升序 void heap_sort(vector<int>&arr,int len) { if (len < 2) return; //heapinsert构建大根堆 //for (int i = 0; i < len; i++) //{ // heapinsert(arr, i); //} //heapfy构建大根堆 for(int i = len - 1; i >=0; i--) { heapify(arr, i, len); } int heapsize = len; swap(arr[0], arr[--heapsize]); while (heapsize > 0) { heapify(arr, 0, heapsize); swap(arr[0], arr[--heapsize]); } } int main() { vector<int>arr = { 1,9,4,8,2,6 }; int len = arr.size(); heap_sort(arr, len); for (auto e : arr) { cout << e << " "; } return 0; }

运行结果：

（2）降序---构建小根堆

#include<iostream> using namespace std; #include<vector> //堆操作--------heapinsert 和 heapfy //某个位置处在index位置上 往上继续移动---------heapinsert操作 void heapinsert(vector<int>& arr, int index) { int parent = (index - 1) / 2; while (arr[index] < arr[parent]) { swap(arr[index], arr[parent]); index = parent; parent = (index - 1) / 2; } } //某个数在index位置，能否往下移动---------heapfy操作 void heapify(vector<int>& arr, int index, int heapsize) { //左孩子下标 int left = 2 * index + 1; //两个孩子中谁大，就把小标给 *** all while (left < heapsize) //左孩子存在 { int *** all; if ((left + 1 < heapsize) && arr[left + 1] < arr[left]) { *** all = left + 1; } else { *** all = left; } if (arr[ *** all] < arr[index]) { *** all = *** all; } else { *** all = index; } if ( *** all == index) { break; } swap(arr[ *** all], arr[index]); index = *** all; left = index * 2 + 1; } } //堆排序,降序 void heap_sort(vector<int>& arr, int len) { if (len < 2) return; //heapinsert构建小根堆 for (int i = 0; i < len; i++) { heapinsert(arr, i); } //heapfy构建小根堆 //for (int i = len - 1; i >= 0; i--) //{ // heapify(arr, i, len); //} int heapsize = len; swap(arr[0], arr[--heapsize]); while (heapsize > 0) { heapify(arr, 0, heapsize); swap(arr[0], arr[--heapsize]); } } int main() { vector<int> arr = { 1,9,4,8,2,6 }; //for (int i = 0; i < arr.size(); i++) //{ // heapinsert(arr, i); //} //for (int i = arr.size() - 1; i >= 0; i--) //{ // heapify(arr, i, arr.size()); //} heap_sort(arr, arr.size()); for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } return 0; }

运行结果：

算法特性

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定