完成阅读您将会了解堆排序的：

1. 算法思想
2. 实现步骤
3. 实践范例（C++/Rust）

1. 算法思想

堆排序（Heap Sort）是数据结构堆的一个具体应用，由 J. W. J. Williams 在1964年发表的堆排序^[1]提出。关于堆的介绍请前往数据结构堆查看。

在堆的基础上，每次取出堆顶，再维护剩余堆的性质即可完成堆排序，如图1^[2]。堆排序时间复杂度为\(\Theta(n\lg n)\)，空间复杂度\(\Theta(1)\)。堆排序是原址排序（In-place Sort），但它是不稳定的排序算法。关于排序的稳定性，请前往快速排序查看。

图1：堆排序

2. 实现步骤

1. 待排序序列构建为堆；
2. 交换堆顶与堆尾；
3. 更新堆大小；
4. 从堆顶开始堆化；
5. 重复以上过程直至堆大小为1。

3. 实践范例（C++/Rust）

问题描述：
为无序数组A做单调不减排序。
输入：无序数组A
输出：有序数组A
解答思路：
运用对堆排序算法对A进行原址排序。

---

伪代码1：堆化
变量说明：H\(\rightarrow\)堆数组；i\(\rightarrow\)堆化始发下标；left\(\rightarrow\)左子节点下标；right\(\rightarrow\) 右子节点下标

\[\begin{aligned} &HEAPIFY(H,i,size)\\ &~~~~~~left \leftarrow 2i + 1 \\ &~~~~~~right \leftarrow left + 1\\ &~~~~~~while ~~~left < size \\ &~~~~~~~~~~~~if ~~~H[i] < H[left]\\ &~~~~~~~~~~~~~~~~~~largest \leftarrow left\\ &~~~~~~~~~~~~if ~~~right< size~~~ and~~~ H[largest] < H[right]\\ &~~~~~~~~~~~~~~~~~~largest \leftarrow right\\ &~~~~~~~~~~~~if ~~~largest \ne i\\ &~~~~~~~~~~~~~~~~~~swap(H[i], H[largest])\\ &~~~~~~~~~~~~~~~~~~i \leftarrow largest\\ &~~~~~~~~~~~~left \leftarrow 2i + 1\\ &~~~~~~~~~~~~right \leftarrow left + 1 \end{aligned} \]

伪代码2：堆排序
变量说明：A\(\rightarrow\)待排序序列

\[\begin{aligned} &HEAP\_SORT(A)\\ &~~~~~~size\leftarrow A.size\\ &~~~~~~for~~~i\leftarrow \frac{size}{2} -1~~~ downto ~~~ 0\\ &~~~~~~~~~~~~HEAPIFY(H,i,size)\\ &~~~~~~while~~~size>1\\ &~~~~~~~~~~~~size\leftarrow size-1\\ &~~~~~~~~~~~~swap(H[0],H[size])\\ &~~~~~~~~~~~~HEAPIFY(H,0,size) \end{aligned} \]

---

C++解答：

void _heapfy(auto H, auto i, auto heap_size) noexcept {
  auto right = i + 1 << 1, left = right - 1;
  while (left < heap_size) {
    auto largest = H[i] < H[left] ? left : i;
    largest = right < heap_size && H[largest] < H[right] ? right : largest;
    if (largest == i)
      break;
    std::swap(H[i], H[largest]);
    i = largest;
    right = i + 1 << 1;
    left = right - 1;
  }
}

void heap_sort(auto A, auto s) noexcept {
  auto i = s >> 1;
  while (i)
    _heapfy(A, --i, s);
  while (s > 1) {
    std::swap(*A, A[--s]);
    _heapfy(A, 0, s);
  }
}

Rust解答：

fn _heapfy<T: std::cmp::PartialOrd>(H: &mut [T], mut i: usize, mut size: usize) {
    let mut right = i + 1 << 1;
    let mut left = right - 1;
    while left < size {
        let mut largest = if H[i] < H[left] { left } else { i };
        largest = if right < size && H[largest] < H[right] { right } else { largest };
        if largest == i { break; }
        H.swap(i, largest);
        i = largest;
        right = i + 1 << 1;
        left = right - 1;
    }
}

pub fn heap_sort<T:std::cmp::PartialOrd>(A:&mut [T]){
    let mut s=A.len();
    let mut i=s>>1;
    while i>0 {
        i-=1;
        _heapfy(A, i, s);
    }
    while s>1{
        s-=1;
        A.swap(0,s);
        _heapfy(A,0,s);
    }
}

4. 自我测试

伪代码实践：
N/A
LeetCode选荐：
N/A

让每一天足够精致，期待与您的再次相遇! ^_^

---

1. Williams JW. Algorithm 232: heapsort. Commun. ACM. 1964;7:347-8. ↩︎

2. 图片引自Wikipedia，在此鸣谢。 ↩︎