算法|堆排序

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

  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,在此鸣谢。 ↩︎

上一篇:AT3913 XOR Tree 题解


下一篇:thusc2021题解