[算法导论] 堆排序

2019-12-09

学习《算法导论》堆排序算法,做了一些笔记。测试源码在 (github)


1. 堆

堆可以看成一个近似的完全二叉树,除了底层外,该树是完全充满的,而且是从左到右填充。

完全二叉树适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。

最大堆中,是指除了根结点外(根结点没有 parent),所有结点的 i 都应该满足: \(A[PARENT(i)] \ge A[i]\)

堆数据-数组-二叉树

堆被看作是一个完全二叉树,那么该堆堆高度成正比 $O(lgn)$ ,我们会发现,堆结构上的一些基本操作的运行时间至多与树的高度成正比,即实际复杂度为 $O(lgn)$。

1
2
3
int parent(int i) { return i / 2; }
int left(int i) { return i << 1; }
int right(int i) { return (i << 1) + 1; }

2. 堆排序过程

MAX-HEAPIFY(堆化):将堆的末端子节点作调整,使得子节点永远小于父节点。

BUILD-MAX-HEAD(建堆):从无序数据数组中构造一个最大堆。

HEAPSORT(排序):对数组进行原址排序,移除位在第一个数据的根节点,并做最大堆调整的递归运算。


2.1. 堆化

堆化让数值大的结点往上浮,让小的结点逐渐下沉。

堆化流程

堆化伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void max_heapify(int array[], int size, int i) {
    int largest = i;
    int l = left(i);
    int r = right(i);

    if (l <= size && array[l] > array[i]) {
        largest = l;
    }

    if (r <= size && array[r] > array[largest]) {
        largest = r;
    }

    if (largest != i) {
        swap(&array[largest], &array[i]);
        max_heapify(array, size, largest);
    }
}

2.2. 建堆

通过二叉树结点自底向上的方法,利用堆化过程,把一个大小为 n = A.length 的数组 A = [1…n] 转换为最大堆。BUILD-MAX-HEAP 时间复杂度为 $O(n)$

建堆伪代码

1
2
3
4
5
void build_max_heap(int array[], int len) {
    for (int i = (len / 2); i >= 1; i--) {
        max_heapify(array, len, i);
    }
}

2.3. 排序

BUILD-MAX-HEAP 会将数组 A[1…n] 建成最大堆。最大堆元素在根结点 A[1],去掉 A[1] 后,A[1] 的左右孩子结点仍然是最大堆。如果把 A[n] 替换 A[1],破坏了最大堆性质,将重新对 A[1…n-1] 数组进行堆化,使其变成最大堆。如此递归重复以上步骤。

排序流程

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void heap_sort::heap_sort() {
    if (m_data_size <= 1) {
        return;
    }

    // 建堆处理后,父结点 > 子结点
    build_max_heap(m_array, m_data_size);
    // 建堆后,堆顶结点(根结点)是最大数值,把最大值放到数组最后。原数组最后一个结点置换到根结点。
    swap(&m_array[1], &m_array[m_data_size]);

    // 排除数组最后一个元素,再对剩余堆进行堆化,再把堆化的根结点放到数组最后。
    m_data_size--;

    // 从上到下(父节点到子树结点)
    while (m_data_size > 1) {
        max_heapify(m_array, m_data_size, 1);
        swap(&m_array[1], &m_array[m_data_size]);
        m_data_size--;
    }
}

3. 优先队列

在计算机系统的作业调度中,任务需要根据优先级进行执行。可以根据堆算法(最大堆),每个任务都赋予一个优先级数值,选出最高优先级(最大堆堆顶)作业任务执行。涉及任务处理,一般都有增删改查的操作。 理解了建堆,堆化和排序的流程,队列的这些操作应该都比较好理解了。


3.1. HEAP-MAXINUM

获取堆顶元素,时间复杂度为 $O(1)$

获取堆顶元素

1
2
3
4
5
6
7
8
9
10
bool heap_sort::heap_maxinum(int& n) {
    if (m_data_size <= 0) {
        return false;
    }
    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }
    n = m_array[1];
    return true;
}

3.2. HEAP-EXTRACT-MAX

删除堆顶元素,时间复杂度为 $O(n)$

删除堆顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool heap_sort::heap_extract_max(int& n) {
    if (m_data_size <= 0) {
        return false;
    }

    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }

    n = m_array[1];
    swap(&m_array[1], &m_array[m_data_size]);
    m_data_size--;
    max_heapify(m_array, m_data_size, 1);
    return true;
}

3.3. HEAP-INCREASE-KEY

增加堆指定元素(任务)的数值,HEAP-INCREASE-KEY 时间复杂度为 $O(lgn)$

增加数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool heap_sort::heap_increase_key(int i, int key) {
    if (i < 1 || m_data_size <= 0 || key < m_array[i]) {
        return false;
    }

    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }

    // 这里跟 build_max_heap 道理一样,只是 build_max_heap
    // 是自底向上,heap_increase_key 是从 i 结点向上
    m_array[i] = key;
    while (parent(i) > 0 && m_array[parent(i)] < m_array[i]) {
        swap(m_array[parent(i)], m_array[i]);
        i = parent(i);
    }
    return true;
}

3.4. MAX-HEAP-INSERT

插入新元素到最大堆末位,也就是在最大堆上增加一个叶子,叶子自下而上与它的父结点比较替换。运行时间复杂度为 $O(lgn)$

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool heap_sort::max_heap_insert(int key) {
    if (m_data_size >= m_data_len) {
        return false;
    }

    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }

    // 将结点放置数组末位,也就是在最大堆上增加一个叶子,叶子自下而上与它的父结点比较替换。
    m_data_size++;
    m_array[m_data_size] = key;

    // 这是 heap_increase_key 主逻辑的实现。
    int i = m_data_size;
    while (parent(i) > 0 && m_array[parent(i)] < m_array[i]) {
        swap(m_array[parent(i)], m_array[i]);
        i = parent(i);
    }

    return true;
}

4. 参考