《编程珠玑》第14章 堆排序与优先队列

第14章中介绍了一种常用的数据结构“堆”,并用它解决了两个重要问题。

  • 排序,使用堆排序算法对元数组排序,时间复杂度为
  • 优先级队列,堆通过插入元素和提取堆顶元素来维护元素集合,每个操作所需的时间都是

1.堆的介绍

  • 堆是一种二叉树,由下面的两条性质决定:

    • 顺序性质:按树中任何结点与其子结点的值的大小关系,可以分为大根堆小根堆两种。大根堆要求任何结点的值都大于或等于其子结点的值,意味着根结点就是集合的最大元素。对应的,小根堆要求任何结点的值都小于或等于其子结点的值。
    • 形状性质:堆是一种完全二叉树,要求叶子结点只能在最后的两层出现,除最后一层外,其余各层的结点数达到最大值,最底层的结点都连续集中在最左边。对于一个具有个结点的堆,它的高度为
  • 这两个性质具有足够的限制性,使得我们可以找到集合中的最值;但也有足够的灵活性,使得我们在插入或删除一个元素之后可以有效地重新组织结构。

    a

  • 下面考虑一下怎么表示堆,最常见的二叉树的表示方法就是使用指针。但是堆是一种完全二叉树,我们可以利用数组下标来隐式的表示,即数组元素的顺序就是堆的层次遍历的结果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //返回左子节点下标
    int Left(int i){
    return 2 * i + 1;
    }

    //返回右子节点下标
    int Right(int i){
    return 2 * (i + 1);
    }

2. 关键函数:堆性质的维护函数

  • 这里研究一个重要的函数,用于在数组的某一段不再满足堆性质时进行调整。
  • 这里选择自上而下的方向进行调整,并使用《算法导论》里的递归形式来实现一个大根堆

  • 考虑一个以为根的大根堆分别表示它的左右子结点,当的值改变时,我们需要重新调整来维护堆性质。现在可以断言的是以为根的子树一定是大根堆,如果,则堆性质依然满足,算法结束;如果子结点中存在一个更大的值,应该将互换,但此时以为根的子树的堆性质可能会被破坏,所以需要对它进行递归维护。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //维护一个以root为根的,末尾下标为len大根堆
    void MaxHeapify(vector<int>& heap, int root, int len){
    int left = Left(root);
    int right = Right(root);
    int largest;//保存左右子树中的最大值
    //先比较左子树
    if (left <= len && heap[left] > heap[root])
    largest = left;
    else
    largest = root;
    //比较右子树
    if (right <= len && heap[right] > heap[largest])
    largest = right;
    //子节点中有更大的数
    if (largest != root){
    swap(heap[root], heap[largest]);
    //交换之后可能破坏子树的大根堆性质,递归下去维护
    MaxHeapify(heap, largest, len);
    }
    }

3. 堆排序

  • 给定一个数组,使用堆按升序排序其中的元素。

  • 首先需要在数组上初始一个大根堆,这里使用自下而上的方法。

    init

    1
    2
    3
    4
    5
    6
    7
    8
    //自底向上建大根堆
    void BuildMaxHeap(vector<int>& heap){
    //最后一个叶节点的双亲节点
    int lastParent = heap.size() / 2 - 1;
    for (int i = lastParent; i >= 0; i--){
    MaxHeapify(heap, i, heap.size()-1);
    }
    }
  • 因为大根堆保证堆顶都是最大值,所以可以使用循环交换首尾元素,再重新调整新范围内的元素来排序整个数组。

    sort

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //堆排序
    void HeapSort(vector<int>& heap){
    //建大根堆
    BuildMaxHeap(heap);
    //每次将堆顶和末尾元素交换
    for (int i = heap.size() - 1; i >= 1; i--){
    swap(heap[0], heap[i]);
    //因为堆顶和末尾交换了,维护这个堆
    MaxHeapify(heap, 0, i - 1);
    }
    }

4. 优先级队列

4.1 插入操作

  • 首先考虑一个常用操作:向队列中插入新的元素。对于数组来说,在尾部插入新元素的代价是最小的。插入之后则需要从底部开始做调整来维护堆性质。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //将下标index节点的值变成k
    void Update(vector<int>& Q, int index, int k){
    if (k >= Q[index]){
    Q[index] = k;
    //向上维护堆
    while (index > 0 && Q[(index - 1)/ 2] < Q[index]){
    swap(Q[(index - 1) / 2], Q[index]);
    index = (index - 1) / 2;
    }
    }
    }

    //向队列插入节点
    void Insert(vector<int>& Q, int k){
    Q.push_back(INT_MIN);
    Update(Q, Q.size()-1, k);
    }

4.2 取队列的头元素

  • 这里简单,在数组非空时直接返回数组的首元素即可。

    1
    2
    3
    4
    5
    6
    7
    //返回优先队列的队头元素
    int getFront(vector<int>& Q){
    if (Q.empty())
    return INT_MIN;
    else
    return Q[0];
    }

4.3 删除队列的头元素

  • 因为在数组中删除元素时最简单的情形就是删除末尾元素,所以可以先将首尾元素互换之后再删除尾元素。再重新调整来维护堆性质。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //删除队头元素
    void popMax(vector<int>& Q){
    if (Q.empty())
    cout << "队空,不能删除" << endl;
    else{
    swap(Q[0], Q.back());
    Q.pop_back();
    MaxHeapify(Q, 0, Q.size() - 1);
    }
    }
------------- 本文结束 感谢您的阅读 -------------

本文标题:《编程珠玑》第14章 堆排序与优先队列

文章作者:Perry

发布时间:2019年09月01日 - 16:05

最后更新:2019年09月19日 - 13:47

原始链接:https://perry96.com/archives/ef26fa0d.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%