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

2024-05-01 06:52:07
开发
27

一、堆结构和堆排序

（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;
}

四、计算复杂度

总结堆结构

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

堆排序

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

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

原文地址:https://blog.csdn.net/weixin_41987016/article/details/138362120 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1785442032660123648.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部

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

相关推荐

最近更新

热门阅读