堆排序(heapsort)

前言

堆排序是 排序 算法中的一种，算法时间复杂度是O(n log(n))。这里主要介绍 堆的构建 以及怎样通过 heapify操作 完成 堆排序 。代码是用 C语言 完成的，算法不难，大家可以自己用其他语言实现一下。

什么是堆（Heap）

Heap需要满足两个条件：

1.Complete Binary Tree :需要是一颗完全二叉树
2.Parent > Children:父节点的值一定要大于子节点的值

什么是完全二叉树

生成节点的顺序是从上往下、从左往右依次生成

如下图所示：

父节点的值大于子节点的值

如下图所示：

怎么样用代码表示堆

1.假设先有这样一颗完全二叉树，它已经是一个堆了

2.1 我们按照从上往下、从左往右的顺序对每个节点数字进行编号，

2.2 我们可以用一个一维数组表示

2.3 使用数组的下标来表示一个完全二叉树的好处就是从任何一个节点出发我都可以通过计算来拿到这个节点的父节点和子节点

构建堆

1.假设拿到了一堆数字：10 4 3 5 1 2，这些数字放在了一颗完全二叉树上面，如下图所示：

2.heapify:

把完全二叉树调整成堆，我们把这种操作起个名字叫：heapify

1.第一次heapify操作：把4（父节点）、10、3这三个子节点进行比较，找到最大值和父节点进行交换

交换后如下图:

2.第二次heapify操作,把4（父节点）、5、1这三个子节点进行比较，找到最大值和父节点进行交换

交换后如下图:

3.这样我们就生成了一个堆：满足完全二叉树、父节点值大于子节点的值

123步的代码实现：

void swap(int *tree, int max, int i) {
        int temp = tree[i];
        tree[i] = tree[max];
        tree[max] = temp;
    }
    
    /**
     对一个二叉树进行heapify操作
    
     @param tree 表示二叉树的数组
     @param n 二叉树的节点个数
     @param i 表示要对哪个节点进行heapify操作
     */
    void heapify(int *tree, int n, int i) {
        if (i >= n) { // 递归函数出口
            return;
        }
        // 找到i节点的两个子节点
        int c1 = i*2 + 1;
        int c2 = i*2 + 2;
        // 找个三个节点的最大值 假设i是最大值
        int max = i;
        if(c1 < n && tree[c1] > tree[max]) { // c1 < n 表示节点下面没有子节点
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]) {
            max = c2;
        }
        if (max != i) { // max != i b如果i已经是最大值了就不用交换了
            swap(tree, max, i);
            heapify(tree, n, max);//max节点继续heapify
        }
    }
    
    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            int tree[] = {4,10,3,5,1,2};
            int n = 6;
            heapify(tree, n, 0);
            
            for (int i = 0; i < n; i++) {
                printf("%d\n", tree[i]);
            }
        }
        return 0;
    }

输出结果：

4.如果一棵完全二叉树的节点的值都是乱序，我们就可以从倒数第二层开始往上对每个节点进行heapify，流程如下：

1.

2.

3.

4.

代码实现：

void buildHeap(int *tree, int n) {
        int lastNode = n-1;
        int parent = (lastNode-1)/2;
        for (int i = parent; i>=0; i--) {
            heapify(tree, n, i);
        }
    }
    
    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            int tree1[] = {2,5,3,1,10,4};
            int m = 6;
            buildHeap(tree1, m);
            for (int i = 0; i < m; i++) {
                printf("%d\n", tree1[i]);
            }
        }
        return 0;
    }

输出结果：

画出树结构：

堆排序 heapsort

1.假设有一棵树是堆的结构，所以父节点大于子节点，且根节点是最大的

2.首先第一步，根节点和最后一个节点交换，这样最大节点就跑到最后一位

3.第二步把最后一位节点砍断

4.因为刚刚做了第一步的交换，我们就破坏了堆结构，所以我们要做heapify，以此类推

代码实现：

void heapSort (int *tree, int n) {
        buildHeap(tree, n);
        for (int i = n-1; i>=0; i--) {
            swap(tree, i, 0);// 交换更节点和末位节点
            heapify(tree, i, 0); //破坏堆结构后做heapify操作
        }
    }
    
    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            int tree[] = {2,5,3,1,10,4};
            int m = 6;
            heapSort(tree, m);
            for (int i = 0; i < m; i++) {
                printf("%d\n", tree[i]);
            }
        }
        return 0;
    }

输出结构：