内容纲要
堆排序的理解和实现
原理
- 将一个无序序列建成一个堆,根据大顶堆或小顶堆的性质,堆顶元素为序列的最大(小)值
- 初始化建堆后,调整输出堆顶的最值元素,对剩余的序列
- 继续调整为大顶堆/小顶堆,调整输出堆顶的最值元素
- 如此循环,直到序列有序,具体过程得需要在代码中体会
可视化堆排序
了解
大(小)顶堆
- 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列
- 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列
以0建堆(类似建二叉树)
- 父节点和子节点关系:左孩子–>son_left = dad*2+1
- 对长度为n的系列建堆,堆的最后一个父节点下标为 len // 2 – 1
以1建堆
- 父节点和子节点关系:左孩子–>son_right = dad*2
- 对长度为n的系列建堆,堆的最后一个父节点下标为 len // 2
C++代码实现
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int> &v,int beg,int end){
int dad = beg; //父节点
int son = dad * 2 + 1; //子节点
while(son <= end){ //如果子节点在待排序序列的范围内,继续循环
//先比较两个子节点大小,选择最大的
if(son < end && v[son] < v[son+1]) son++;
if(v[dad] > v[son]) return ; //父节点值大于子节点值表示调整完毕
else{ //交换父子节点,接着比较子节点和孙节点
swap(v[dad],v[son]);
dad = son; //重置父、子节点下标
son = dad * 2 + 1;
}
}
}
void heap_sort(vector<int> &v){
// 初始化大(小)根堆,i从最后一个父节点开始调整
// 由于以下标0的位置为根结点建堆,最后一个父节点下标为 len/2 -1
int n = v.size();
// 初始化建堆
for(int i = n/2-1;i >= 0;--i){
// 对每一个父节点,通过与子节点(不)交换,完成大(小)顶堆的初始化调整
heapify(v,i,n-1); //调整节点i所在的 子堆(序列) 为大(小)顶堆
}
for(int i = n-1;i > 0;--i){
//自后向前,每一次进行调整,a[0]都会是最大(小)的元素
//将a[0]与待排序序列的最后一位(也即已排好序列的前一位)进行交换
//初始化建堆后seq[0]已经是最大值,交换a[0]和a[n-1]
//最后一次排序时a[0]已经排好,不需要交换
swap(v[0],v[i]);
heapify(v,0,i-1); //调整 交换后的新待排序列 将子堆(序列)调整为大(小)根堆
}
}
int main()
{
vector<int> v;
v.push_back(-4);
v.push_back(-8);
v.push_back(9);
v.push_back(5);
heap_sort(v);
for(int i = 0;i < 4;i++) cout << v[i] << endl;
return 0;
}
Python代码实现
def heapify(seq,beg,end):
dad = beg
son = dad * 2 + 1
while(son <= end):
if(son < end and seq[son] < seq[son+1]):
son += 1
if(seq[dad] > seq[son]):
return
else:
seq[dad],seq[son] = seq[son],seq[dad]
dad = son
son = dad * 2 + 1
def heap_sort(seq):
n = len(seq)
# 初始化建堆
for i in range(n//2-1,-1,-1): # 注意整除
heapify(seq,i,n-1)
# 初始化建堆后seq[0]已经是最大值,交换a[0]和a[n-1]
# 最后一次排序时a[0]已经排好,不需要交换
for i in range(n - 1,0,-1):
seq[0],seq[i] = seq[i],seq[0]
heapify(seq,0,i - 1)
# 排序测试
if __name__ == '__main__':
seq = [3,-4,22,-8,47,15,36,26,27,50]
heap_sort(seq)
print(seq)