当前位置：首页 > ops >正文

堆排序的详细解读

ops 2025/6/26 4:19:03

一.堆的基本概念

1.什么是堆

堆是一种特殊的完全二叉树，满足一下性质：

最大堆：每个节点的值都大于或等于其子节点的值（堆顶元素最大）
最小堆：每个节点的值都小于或等于其子节点的值（堆顶元素最小）

其中，堆排序常使用最大堆来进行升序排序

2.堆的存储

堆常用数组进行存储，对于数组中第i个元素：

父节点的位置：(i-1)/2
左节点的位置：2*i+1
右节点的位置：2*i+2

二、堆排序的基本思想

堆排序的基本思想分为两个主要步骤：
1. 建堆：将无序数组构建成一个最大堆
2. 排序：重复从堆中取出最大元素（堆顶），然后调整剩余元素使其重新成为最大堆

三、堆排序的详细步骤

1. 构建最大堆
从最后一个非叶子节点开始（即n/2 - 1），向前依次对每个节点执行"下沉"操作，确保以该节点为根的子树满足堆的性质。

下沉操作：
1. 比较当前节点与其左右子节点
2. 如果当前节点小于某个子节点，则与较大的子节点交换
3. 继续向下比较，直到当前节点大于等于其子节点或到达叶子节点

2. 排序过程
1. 将堆顶元素（最大值）与堆的最后一个元素交换
2. 堆的大小减1（排除已排序的元素）
3. 对新的堆顶元素执行下沉操作，恢复堆的性质
4. 重复上述过程，直到堆中只剩一个元素

演示：

四、堆排序的代码实现

#include<iostream>
#include<algorithm>using namespace std;//重建堆
void adjust(int a[],int start,int end)
{int temp=a[start];    //根节点for(int i=2*start+1;i<=end;i=i*2+1)   //从左子树开始{if(i<end&&a[i]<a[i+1])    //如果右子树大于左子树，则i指向右子树{i++;}if(a[i]>temp)    //如果子节点大于根节点，则将子节点的值赋给根节点{a[start]=a[i];start=i;}else    //如果子节点小于根节点，则跳出循环{break;}}a[start]=temp;    //将根节点的值赋给子节点
}//堆排序
void heapsort(int a[],int n)
{//建立大根堆for(int i=n/2-1;i>=0;i--)   //从最后一个非叶子节点开始{adjust(a,i,n-1);    //调整堆}//交换堆顶和堆底元素，重新调整堆for(int i=n-1;i>0;i--){swap(a[0],a[i]);    //交换堆顶和堆底元素adjust(a,0,i-1);    //调整堆}
}int main()
{int a[]={46,55,13,42,94,17,5,70};int n=sizeof(a)/sizeof(a[0]);heapsort(a,n);for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
}

五、堆排序的优缺点

优点：
1. 时间复杂度稳定为O(n log n)，没有最坏情况
2. 空间复杂度低，是原地排序算法
3. 适合处理大规模数据

缺点：
1. 不稳定排序算法（相同元素的相对位置可能改变）
2. 在数据量较小的情况下，常数因子较大，可能不如插入排序等简单算法快
3. 数据访问方式不够局部化（缓存不友好）