heap-sort

Introduction to heap and heap sort.

1. 什么是堆

   • 堆（heap）是一种数据结构，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值。
   • 最大堆的父节点的值总是大于其左右孩子的值，最小堆反之。
   • 堆的特性可以用于排序，如果要排序后的顺序为从小到大，则需选择最大堆，反之选择最小堆。

2. 堆排序
   一个无序数组，以升序排序为例，使用堆排序需要以下步骤：

   • 1. 建堆：以无序数组为基础建立最大堆
   • 1. 输出堆顶元素（最大值），将剩余的元素调整为最大堆，反复执行至仅剩一元素，最终输出升序数组
        堆排序通常使用数组实现，时间复杂度为O(NlogN)，空间复杂度为O(1)，是不稳定排序。

3. code

   // 由于堆是完全二叉树，因此可以存储在数组中，某节点i的父结点、左右子结点的索引可以计算得出
   int getParent(int i) {
       return (i - 1) / 2;
   }
   int getLeft(int i) {
       return 2 * i + 1;
   }
   int getRight(int i) {
       return 2 * i + 2;
   }
   // 辅助函数
   void swap(int *a,int *b){
       int temp = *a;
       *a = *b;
       *b = temp;
   }
   // 维护堆的性质：时间复杂度O(logN)
   void holdHeap(vector<int> &arr, int i, int heapSize) {
       int left = getLeft(i),;
       int right = getRight(i);
       int max_i = i;
       if (left < heapSize && arr[left] > arr[max_i])
           max_i = left;
       if (right < heapSize && arr[right] > arr[max_i])
           max_i = right;
       if (max_i != i) {
           swap(arr[i], arr[max_i]);
           holdHeap(arr, max_i, heapSize);
       }
   }
   // 建堆：时间复杂度O(N)
   void buildMaxHeap(vector<int> &arr){
       int heapSize = arr.size();
       for(int i= heapSize/2 - 1; i>=0 ; i--) // 因为是完全二叉树，最后的非叶子结点为 heapSize/2 -  1
           holdMaxHeap(arr, i,heapSize);
   }
   // 堆排序：时间复杂度O(NlogN)
   void heapSort(vector<int> &arr) {
       buildMaxHeap(arr);
       for(int i = arr.size() - 1; i > 0; i--)
       {
           swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
           holdHeap(arr, 0, i);            // 将未完成排序的部分继续进行堆排序
       }
   }