堆排序

一种时间复杂度为 Ο(nlgn) 的排序算法.

二叉堆 是一个数组, 它可以被看成一个近似的完全二叉树, 除了最底层外, 该树是完全充满的, 而且是从左向右填充.

int parent(int i) {
    return i / 2;
}

int left(int i) {
    return 2 * i;
}

int right(int i) {
    return 2 * i + 1;
}

二叉堆分两种形式: 最大堆和最小堆. 在这两种堆中, 结点的值都要满足堆的性质.

  • 在最大堆中 (max-heap) 中, 除了根以外的所有节点 i 都满足:
    • A[PARENT.(i)] ≧ A[i]
  • 在最小堆 (min-heap) 中, 除了根以外的所有节点 i 都满足:
    • A[PARENT.(i)] ≦ A[i]

一般情况下, 我们在堆排序算法中使用最大堆, 在构造优先队列中使用最小堆

Draveness

iOS Developer / Rails / Elixir

Maine, USA draveness.me
blog comments powered by Disqus