【数据结构】-排序-堆排序

堆排序是选择排序中的一种，选择排序的思想是在未排序的数列中选择一个最大或者最小的数据加入已排序序列，大根堆这个结构的根节点就是最大值，因此会大大方便选择。

首先什么是大根堆？

--在完全二叉树中，根>左，右

 关于堆的操作

一.建堆

手动建堆：

第一步：顺序建立一棵树

第二步：检查非叶子结点是否满足 根>左，右，不满足就将当前节点与最大的一个孩子互换（0位置不存储），注意调整上层结点的时候有可能破坏下层的堆结构，此时要继续检查。不断下坠，下坠到无法下坠为止。

算法建堆：

1.从n/2位置开始，逐个非终端节点都要调用AdjustHeap,因为n/2是第一个非叶子节点的序号，所有的叶子节点都已经满足堆的定义了，所以所有的叶子节点都不需要调整。

2.if语句中的条件不能随便安排顺序  if(i<n&&a[i] < a[i + 1]) 如果把这两个条件交换顺序会造成数组越界，也就是说if语句中的条件判断是从左到右顺序执行的。

//调整堆 void adjustHeap(vector<int> &a, int k, int n) { a[0] = a[k];//当前节点的数据暂存到0号位置 for (int i = 2 * k; i <=n; i = i * 2) {//首先指向当前节点的左孩子 if (i<n && a[i] < a[i + 1]) i++;//比较左孩子和右孩子的值，使i永远指向更大的孩子 if (a[0] >=a[i]) break;//当前根节点的值是否比最大的孩子值更大 else { a[k] = a[i];//大孩子存入根 k=i;//更新k,进入下一轮循环，将换入根节点的大孩子作为下一个判断结点 } } a[k] = a[0]; } //建堆 void bulidMaxheap(vector<int> &a,int n) { for (int i=n/2; i > 0; i--)adjustHeap(a, i,n); }

建堆的时间复杂度：n，下面用一个例子说明调整堆的过程：假设已经调整到了最后一个结点k=1

 

二. 删除

1.被删除元素与最后一个节点交换

2.交换后的最后一个结点被剔除在大根堆之外，大根堆元素个数-1

3.重新调整以新元素为根节点的二叉树为堆

注意，一次删除只需要调用一次调整算法即可

三. 建堆+删除实现堆排序

思路：第一步建堆，第二步删除根节点并输出最大值，重新调整剩下的结点

时间复杂度：nlog2n

注意：所谓将堆底元素剥离，实际上是在调整新堆的时候将堆的大小减1，实际还是存在在数组末尾的。

//2.调整堆 void adjustHeap(vector<int> &a, int k, int n) { a[0] = a[k];//当前节点的数据暂存到0号位置 for (int i = 2 * k; i <=n; i = i * 2) {//首先指向当前节点的左孩子 if (i<n && a[i] < a[i + 1]) i++;//比较左孩子和右孩子的值，使i永远指向更大的孩子 if (a[0] >=a[i]) break;//当前根节点的值是否比最大的孩子值更大 else { a[k] = a[i];//大孩子存入根 k=i;//更新k,进入下一轮循环，将换入根节点的大孩子作为下一个判断结点 } } a[k] = a[0]; } //1.建堆 void bulidMaxheap(vector<int> &a,int n) { for (int i=n/2; i > 0; i--)adjustHeap(a, i,n); } //3.主 void heapSort(vector<int> a,int n ) { int temp; bulidMaxheap(a,n);//建堆 for (int i = n; i>1; i--) {//n-1轮 temp = a[1];//a[1]是堆顶元素，a[i]是堆底元素 a[1] = a[i]; a[i] = temp; adjustHeap(a, 1,i-1);//重新调整新堆 } for (int i = 1; i <= n; i++)cout << a[i] << " "; } void Sort() { int n; cout << "请输入元素个数："; cin >> n; vector<int> num(n+1); for (int i = 1; i < n + 1; i++)cin >> num[i]; cout << " 堆排序："; heapSort(num,num.size()-1); } int main() { Sort(); }

 四.插入

将待插入的元素放在堆底，不断的与父节点对比，如果比父节点更小就一路上升，上升到无法上升为止

 

 五.408高频考点：比较次数

插入：一路上深，直到无法上升为止，不会回头比较

删除：一路下坠，直到无法下坠为止，不会回头比较

建堆：左右看，上下看，都要检查！

 

最后在这节的末尾补充完全二叉树的几个规律，再次强调只有在从1位置存储的时候才有这些规律