常见排序:堆排序

Posted on | In

在大二学习数据结构的时候已经学习过堆排序，当时只是理解的很浅，也没机会实现一次。自从开始做LeetCode后一直都在使用Priority_queue，今天有机会就来实现下。

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 (wiki给的解释)

堆:通常是可以被看作成一颗完全二叉树.通常满足下列性质:

  • (大顶堆)堆中孩子节点的值小于其父节点的值

  • (小顶堆)堆中的孩子节点的值大于其父节点的值

  • 堆总是一个完全二叉树

堆就是用数组实现的完全二叉树，所以它没有使用父指针或者子指针。堆根据堆属性排序，堆属性决定了树中节点的位置。由于在数组中，根据数组的下标可以很快的获得当前节点的父节点或则是当前节点子节点。

  • 当前节点的父节点(i - 1) / 2
  • 当前左孩子(i * 2) + 1
  • 当前右孩子(i * 2) + 2

堆的用处:

  • 构建优先队列
  • 支持堆排序
  • 快速找出一个集合中的最小值（或者最大值）

堆的插入

插入某元素完成后要继续保持堆的性质就必须对堆进行调整使其能够继续满足堆的性质.
如下图:

这个堆所对应的数组是{9, 8, 5, 4, 3}
我们插入一个新元素 7

这个时候我们需要调用heapify()调整堆中节点使之成为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void heapify(vector<int>& nums, int start, int n){
        // 调整为大顶堆
        // 其中n为 vector的下标的上界
        if (start >= n ) return ;
        int left_child = start * 2 + 1;         // 左孩子
        int right_child = start * 2 + 2;        // 右孩子
        int max_index = start;                  // 找出 父 左 右 中的最大值
        if (left_child <= n && nums[left_child] > nums[max_index]) 
            max_index = left_child;
        if (right_child <= n && nums[right_child] > nums[max_index]) 
            max_index = right_child;
        if (max_index != start){
            swap(nums[start], nums[max_index]);
            heapify(nums, max_index, n);
        }
    }

建堆

1
2
3
4
5
6
7
8
void buildHeap(vector<int>& nums){
       // 建堆 要从倒数第二层开始建堆
    	// 最后一个节点的父节点开始建堆
       int size = nums.size() - 1;
       int parent = (size - 1) / 2;
       for (int i = parent; i >= 0; --i)
           heapify(nums, i, size);
   }

堆排序

1
2
3
4
5
6
7
8
9
vector<int> heapSort(vector<int>& nums){
       buildHeap(nums);
       int size = nums.size() - 1;
       for (int i = size; i >= 0; --i){
           swap(nums[0], nums[i]);
           heapify(nums, 0, i - 1);	// 每次选取最大值,然后缩小堆的范围
       }
       return nums;
   }

完整的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }
    void heapify(vector<int>& nums, int start, int n){
        // 调整为大顶堆
        // 其中n为 vector的下标的上界
        if (start >= n ) return ;
        int left_child = start * 2 + 1;         // 左孩子
        int right_child = start * 2 + 2;        // 右孩子
        int max_index = start;                  // 找出 父 左 右 中的最大值
        if (left_child <= n && nums[left_child] > nums[max_index]) 
            max_index = left_child;
        if (right_child <= n && nums[right_child] > nums[max_index]) 
            max_index = right_child;
        if (max_index != start){
            swap(nums[start], nums[max_index]);
            heapify(nums, max_index, n);
        }
    }
    void buildHeap(vector<int>& nums){
        // 建堆 要从倒数第二层开始建堆
        int size = nums.size() - 1;
        int parent = (size - 1) / 2;
        for (int i = parent; i >= 0; --i)
            heapify(nums, i, size);
    }
    void heapSort(vector<int>& nums){
        buildHeap(nums);
        int size = nums.size() - 1;
        for (int i = size; i >= 0; --i){
            swap(nums[0], nums[i]);
            heapify(nums, 0, i - 1);
        }
        return ;
    }
};