C++ 堆结构和堆排序（从顶到底/从底到顶的大顶堆）+ 优化

一、堆结构和堆排序 

（1）heapInsert，向上调整大根堆 和 heapify，向下调整大根堆

// i位置的数，向上调整大根堆
// arr[i] = x，x是新来的！往上看，直到不比父亲大，或者来到0位置(顶)
void heapInsert(vector<int>& arr, int i) {
	// i -> 父: (i - 1) / 2
	while (arr[i] > arr[(i - 1) / 2]) {
		swap(arr, i, (i - 1) / 2);
		i = (i - 1) / 2;
	}
}

// i位置的数，变小了，又想维持大根堆结构
// 向下调整大根堆
// 当前堆的大小为size
void heapify(vector<int>& arr, int i, int size) {
	int l = i * 2 + 1;
	
	while (l < size) {
		// 有左孩子，l
		// 右孩子，l+1
		// 评选，最强的孩子，是哪个下标的孩子
		int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
		// 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁
		best = arr[best] > arr[i] ? best : i;
		// 如果最强的下标，是当前的数，那么当前的数已经满足大根堆结构，退出
		if (best == i) { // 最强的是自己
			break;
		}
		swap(arr, best, i);
		i = best;
		l = i * 2 + 1;
	}
}

 二、从顶到底建立大根堆 

 

完整代码：

#include <iostream>
using namespace std;
#include <vector>
 
// 堆结构和堆排序，填函数练习风格
// 测试链接 : https://leetcode.cn/problems/sort-an-array/
 
class heapSort {
public:
	vector<int> sortArray(vector<int> arr) {
		if (arr.size() > 1) {
			// heapSort1 为从顶到底建堆然后排序
			// heapSort2 为从底到顶建堆然后排序
			// 用哪个都可以
			heapSort1(arr);
			//heapSort2(arr);
		}
		return arr;
	}
 
	// i位置的数，向上调整大根堆
	// arr[i] = x，x是新来的！往上看，直到不比父亲大，或者来到0位置(顶)
	void heapInsert(vector<int>& arr, int i) {
		// i -> 父: (i - 1) / 2
		while (arr[i] > arr[(i - 1) / 2]) {
			swap(arr, i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}
 
	// i位置的数，变小了，又想维持大根堆结构
	// 向下调整大根堆
	// 当前堆的大小为size
	void heapify(vector<int>& arr, int i, int size) {
		int l = i * 2 + 1;
		
		while (l < size) {
			// 有左孩子，l
			// 右孩子，l+1
			// 评选，最强的孩子，是哪个下标的孩子
			int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
			// 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁
			best = arr[best] > arr[i] ? best : i;
			// 如果最强的下标，是当前的数，那么当前的数已经满足大根堆结构，退出
			if (best == i) { // 最强的是自己
				break;
			}
			swap(arr, best, i);
			i = best;
			l = i * 2 + 1;
		}
	}
 
	void swap(vector<int>& arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
 
	// 从顶到底建立大根堆，O(n * logn)
	// 依次弹出堆内最大值并排好序，O(n * logn)
	// 整体时间复杂度O(n * logn)
	void heapSort1(vector<int>& arr) {
		int n = arr.size();
		for (int i = 0; i < n; i++) {
			heapInsert(arr, i);
		}
		int size = n;
		while (size > 1) {
			swap(arr, 0, --size);
			heapify(arr, 0, size);
		}
	}
};
 
int main() {
	//vector<int> arr = { 10,0,20,5,89,70,65,45 };
	//vector<int> arr = { 20,30,15,10,9,8,12,45,0,23 };
	vector<int> arr = { 5,6,3,1,9,2,4,6 };
	heapSort hs;
	vector<int> res = hs.sortArray(arr);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << " ";
	}
	cout << endl;
	return 0;
}

三、从底到顶建立大根堆  

依次弹出堆内最大值并排好序

完整代码：

#include <iostream>
using namespace std;
#include <vector>
 
// 堆结构和堆排序，填函数练习风格
// 测试链接 : https://leetcode.cn/problems/sort-an-array/
 
class heapSort {
public:
	vector<int> sortArray(vector<int> arr) {
		if (arr.size() > 1) {
			// heapSort1 为从顶到底建堆然后排序
			// heapSort2 为从底到顶建堆然后排序
			// 用哪个都可以
			//heapSort1(arr);
			heapSort2(arr);
		}
		return arr;
	}
 
	// i位置的数，向上调整大根堆
	// arr[i] = x，x是新来的！往上看，直到不比父亲大，或者来到0位置(顶)
	void heapInsert(vector<int>& arr, int i) {
		// i -> 父: (i - 1) / 2
		while (arr[i] > arr[(i - 1) / 2]) {
			swap(arr, i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}
 
	// i位置的数，变小了，又想维持大根堆结构
	// 向下调整大根堆
	// 当前堆的大小为size
	void heapify(vector<int>& arr, int i, int size) {
		int l = i * 2 + 1;
		
		while (l < size) {
			// 有左孩子，l
			// 右孩子，l+1
			// 评选，最强的孩子，是哪个下标的孩子
			int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
			// 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁
			best = arr[best] > arr[i] ? best : i;
			// 如果最强的下标，是当前的数，那么当前的数已经满足大根堆结构，退出
			if (best == i) { // 最强的是自己
				break;
			}
			swap(arr, best, i);
			i = best;
			l = i * 2 + 1;
		}
	}
 
	void swap(vector<int>& arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
 
	// 从底到顶建立大根堆，O(n)
	// 依次弹出堆内最大值并排好序，O(n * logn)
	// 整体时间复杂度O(n * logn)
	void heapSort2(vector<int>& arr) {
		int n = arr.size();
		for (int i = n - 1; i >= 0; i--) {
			heapify(arr, i, n);
		}
		int size = n;
		while (size > 1) {
			swap(arr, 0, --size);
			heapify(arr, 0, size);
		}
	}
};
 
int main() {
	//vector<int> arr = { 10,0,20,5,89,70,65,45 };
	//vector<int> arr = { 20,30,15,10,9,8,12,45,0,23 };
	vector<int> arr = { 5,6,3,1,9,2,4,6 };
	heapSort hs;
	vector<int> res = hs.sortArray(arr);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << " ";
	}
	cout << endl;
	return 0;
}

四、计算复杂度 

总结堆结构

1. 完全二叉树和数组前缀范围的对应
2. i的父亲节点：(i-1)/2，i的左孩子：i*2+1，i的左孩子：i*2+2
3. 堆的定义（大根堆，小根堆），本节课讲解按照大根堆来讲解，小根堆是同理的
4. 堆的调整：heapInsert（向上调整），heapify（向下调整）
5. heapInsert、heapify方法的单次调用，时间复杂度O(logn)，完全二叉树的结构决定的

堆排序

• A.从顶到底建堆，时间复杂度O(n*logn)，log1 + log2 + log3 + ... + logn -> O(n*logn)
• B.从底到顶建堆，时间复杂度O(n)，总代价就是简单的等比数列关系，为啥会有差异？简单图解一下
• C.建好堆之后的调整阶段，从最大值到最小值依次归位，时间复杂度O(n*logn)，不管以什么方式建堆，调整阶段的时间复杂度都是这个 ，所以整体复杂度也是这个额外空间复杂度是O(1)，因为堆直接建立在了要排序的数组上，所以没有什么额外空间

注意:堆结构比堆排序有用的多，尤其是和比较器结合之后，后面博客会重点讲述