堆排序的理解和实现

原理

1. 将一个无序序列建成一个堆,根据大顶堆或小顶堆的性质，堆顶元素为序列的最大(小)值
2. 初始化建堆后，调整输出堆顶的最值元素，对剩余的序列
3. 继续调整为大顶堆/小顶堆，调整输出堆顶的最值元素
4. 如此循环，直到序列有序,具体过程得需要在代码中体会

可视化堆排序

了解

大(小)顶堆

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

以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)