Fork me on GitHub

优先队列1--堆

发表于   |     |   阅读次数

继续是《数据结构算法与应用：C++语言描述》的笔记，这是第九章优先队列的内容。本小节主要介绍的是优先队列的定义以及其中一种实现方法—最大堆的实现，最后是堆的一个应用—堆排序。

优先队列删除元素时根据优先权高或低的次序，而不是元素进行队列的次序，这与之前第六章介绍的FIFO结构的队列不同。

可以利用堆数据结构来高效地实现优先队列，堆是一棵完全二叉树。

引言

优先队列（priority queue)是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有1）查找；2）插入一个新元素；3）删除。

优先队列可以按搜索的是优先权大或小的元素分为最大优先队列或者最小优先队列，而删除操作则是用来删除对应查找的元素。另外，优先队列中的元素可以有相同的优先权，查找和删除操作可根据任意优先权进行。

下面给出最大优先队列的抽象数据类型，最小优先队列的抽象数据类型与之相似，只需要将最大改为最小。

1
2
3
4
5
6
7
8
9
10
抽象数据类型MaxPriorityQueue{
实例
    有限的元素集合，每个元素都有一个优先权
操作
    Create(): 创建一个空的优先队列
    Size(): 返回队列中的元素数目
    Max(): 返回具有最大优先权的元素
    Insert(x): 将x插入队列
    DeleteMax(x): 从队列中删除具有最大优先权的元素，并将该元素返回至x
}

堆

定义

[最大树（最小树）] 每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。

最大树与最小树的例子分别如下图9-1,9-2所示。虽然这些树都是二叉树，但最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于2。

此处输入图片的描述

[最大堆(最小堆)] 最大（最小）的完全二叉树。

上图9-1b并所示的最大树并不是最大堆，因为它不是完全二叉树，而其他两个最大树是最大堆。同样，图9-2b也不是完全二叉树，所以也不是最小堆，其他两个最小树则是最小堆。

堆是完成二叉树，可以利用二叉树的基本概念和实现中介绍的公式化描述方案，可用一维数组有效地描述堆，利用二叉树的特性4可将堆中的节点移动到其父节点或子节点处。另外，堆是完全二叉树，拥有n个元素的堆高度是$\left\lceil log_2(n+1) \right\rceil$,因此，如果可在$O(height)$时间内完成插入和删除操作，其复杂性是$O(log_2n)$。

最大堆的插入

如下图9-3a是一个具有5个元素的最大堆，当要加入一个元素的时候，因为堆是完全二叉树，得到的新树结构必然如9-3b所示，这个时候如果新元素的值是5，它比2要大，此时需要将2下移变成左孩子，如图9-3c所示，此外还要与根节点进行比较，这里如果新插入的元素值是21，就大于根节点的20了，此时还需要将20下移到原来2的位置，变成如图9-3d所示。

此处输入图片的描述

插入策略从叶到根只有单一路径，每层工作需耗时$\theta(1)$,因此实现此策略的时间复杂性是$O(height)=O(log_2n)$。

最大堆的删除

假设对图9-3d的最大堆进行删除，需要删除的是元素21，这个时候只剩下5个元素，需要重新构建最大堆的结构，那么最终应该得到如图9-3a的最大堆形式。然后接下来要删除的是元素20，并得到如图9-4b所示的结构，则首先10从位置5移出，但将其放在根节点的位置得到的不是最大堆，则把根节点的两个孩子15和2中较大的一个放到根节点，然后假设将10插入位置2，但是还不是最大堆，因此将14上移到位置2,10放到位置4，得到如图9-4c所示。

此处输入图片的描述

删除策略如插入策略一样，从堆的根节点到叶节点只有单一路径，每层工作需耗时$\theta(1)$,因此实现此策略的时间复杂性是$O(height)=O(log_2n)$。

最大堆的初始化

现在假设开始有数组a，它有n个元素，n=10，它可以用如图9-5a所示的完全二叉树表示，但它不是最大堆。为了将其转化为最大堆，从第一个具有孩子的节点开始（即节点10），这个元素在数组中的位置是$i=[n/2]$，如果以这个元素为根的子树已经是最大堆，则不需要调整，否则必须调整子树成为最大堆，然后继续检查$i-1,i-2,\ldots$等节点为根的子树，直到检查到根节点为止。

对图9-5a所示的完全二叉树，首先i=5，因为$10>1$,所以以位置i为根的子树已经是最大堆，接下来检查位置4的子树，$15<17$,它不是最大堆，将其变为最大堆，可得到如图9-5b所示，然后依次检查位置3，位置2以及根节点，分别得到如图9-5c，d所示的最大堆。

此处输入图片的描述

类MaxHeap

下面程序给出最大堆的类定义。n是私有成员，代表目前堆中的元素的个数；MaxSize是堆的最大容量；heap是存储堆元素的数组，默认大小是10。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
class MaxHeap{
private:
    int CurrentSize, MaxSize;
    T* heap;
public:
    MaxHeap(int MaxHeapSize = 10);
    ~MaxHeap(){ delete[] heap; }
    int Size() const{ return CurrentSize; }
    T Max(){
        if (CurrentSize == 0)
            throw OutOfBounds();
        return heap[1];
    }
    MaxHeap<T>& Insert(const T& x);
    MaxHeap<T>& DeleteMax(T& x);
    void Initialize(T a[], int size, int ArraySize);
};

下面给出最大堆的插入、删除和初始化代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x){
    // 将x插入到最大堆中
    if (CurrentSize == MaxSize)
        throw NoMem();

    // 为x寻找插入位置
    int i = ++CurrentSize;
    while (i != 1 && x > heap[i / 2]){
        // 不能够将x放入heap[i]
        heap[i] = heap[i / 2];  // 将元素下移
        i /= 2; // 移向父节点
    }

    heap[i] = x;
    return *this;
}

template<class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x){
    // 将最大元素放入x，并从堆中删除最大元素
    if (CurrentSize == 0)
        throw OutOfBounds();

    x = heap[1];    // 最大元素

    // 重构堆
    T y = heap[CurrentSize--];  // 最后一个元素

    // 从根开始，为y寻找合适的位置
    int i = 1, ci = 2;
    while (ci <= CurrentSize){
        // heap[ci]应是i较大的孩子
        if (ci < CurrentSize && heap[ci] < heap[ci + 1])
            ci++;

        // 判断是否能将y放入heap[i]
        if (y >= heap[ci])
            break;

        // 不能
        heap[i] = heap[ci];
        // 下移一层
        i = ci;
        ci *= 2;
    }
    heap[i] = y;

    return *this;
}

template<class T>
void MaxHeap<T>::Initialize(T a[], int size, int ArraySize){
    // 把最大堆初始化为a
    delete[] heap;
    heap = new T[size + 1];
    for (int s = 1; s <= size; s++){
        heap[s] = a[s - 1];
    }
    CurrentSize = size;
    MaxSize = ArraySize;

    //产生一个最大堆
    for (int i = CurrentSize / 2; i >= 1; i--){
        T y = heap[i];

        // 寻找放置y的位置
        int c = 2 * i;
        while (c <= CurrentSize){
            if (c < CurrentSize&&heap[c] < heap[c + 1])
                c++;

            if (y >= heap[c])
                break;

            heap[c / 2] = heap[c];
            c *= 2;
        }
        heap[c / 2] = y;
    }
}

插入代码中，i从新创建的叶节点位置CurrentSize开始，对从该位置到根的路径进行遍历，对每个位置，都检查是否到达跟(i=1)或在i处插入新元素不会改变最大树的性质—$x \le heap[i/2]$，只要满足其中一个条件，就可以在i处插入x，否则会执行循环体中的代码。插入操作的时间复杂性是$O(logn)$。

删除操作的时间复杂性也是$O(logn)$。

初始化函数Initialize中for循环每次所花时间是$O(logn)$,循环次数是n/2，总的复杂性是$O(nlogn)$。实际应用中，初始化操作的复杂性是$\theta(n)$。

更完整的代码例子可以查看最大堆的实现。

堆排序

利用堆来实现n个元素的排序，所需时间是$O(nlogn)$,可以将先要排序的n个元素初始化为一个最大堆，然后每次从堆中提取（即删除）元素，各元素将按递减次序排列。初始化所需要的时间是$\theta(n)$,每次删除所需要的时间是$O(logn)$,因此总时间是$O(nlogn)$。

实现代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void HeapSort(T a[], int n){
    // 利用堆排序算法对a[1:n]进行排序
    MaxHeap<T> H(1);
    H.Initialize(a, n, n);

    // 从最大堆中逐个抽取元素
    T x;
    for (int i=n - 1; i >= 0; i--){
        H.DeleteMax(x);
        a[i] = x;
    }

    // 在堆的析构函数中保存数组a
    H.Deactivate();
}

测试例子如下：

1
2
3
4
5
6
7
8
9
10
11
int main(void){
    int a[] = { 20, 12, 35, 15, 10, 80, 30, 17, 2, 1 };
    HeapSort(a, 10);
    for (int i = 0; i < 10; i++)
        cout << a[i] << ", ";

    cout << "\n";

    system("pause");
    return 0;
}

输出如下图所示：

此处输入图片的描述