专注于做有价值的技术原创

0%

数据结构基础知识: 表 栈 队列 树 散列 堆

发表于 分类于

1. 表，栈和队列

表，栈和队列是计算机科学中最简单和最基本的三种底层数据结构。事实上，每一个有意义的程序都将明晰地至少使用一种这样的数据结构，而栈则在程序中总是要间接地用到，不管你在程序中是否做了声明。

1.1 抽象数据类型（ADT）

在计算机软件编程中，我们会接触到诸如整型，浮点型，字符型，布尔型等基本数据类型，也有一些更为复杂的复合数据类型，如数组，字典（散列表），元组等。如果我们抛开这些数据类型具体实现，进一步抽象，给出更一般的定义，即每一种数据类型实际是一些特定操作的集合。我们称这些操作的集合为抽象数据类型（abstract data type, ADT）。ADT 是数学意义上的抽象，它不约束各个操作的具体实现，对于每种 ADT 并不存在什么法则来告诉我们必须要有哪些操作，这只是一个设计决策。

1.2 表ADT

表是一种形如 A_1, A_2, A_3, \ldots, A_N 的数据结构。我们说这个表的大小是 N 。我们称大小为 0 的表为空表(empty list)。对于除空表以外的任何表，我们说 A_{i+1}(i<N) 后继 A_i （或继 A_i 之后）并称 A_{i-1}(i>1) 前驱 A_i 。定义表ADT的操作集合通常包含：

  • PrintList: 打印表
  • MakeEmpty: 返回空表
  • Find: 返回关键字(key)首次出现的位置
  • Insert: 从表的指定位置插入关键字(key)
  • Delelte: 从表的指定位置删除关键字(key)
  • FindKth: 返回指定位置上的元素

1.2.1 简单数组实现

我们最容易想到实现表的方法就是数组。使用数组实现表的各项操作，显而易见的时间复杂度是:

  • PrintList: O(N)
  • Find: O(N)
  • FindKth: O(1)
  • Insert: O(N)
  • Delete: O(N)

我们不难发现，当插入和删除 N 个元素时，需要花费 O(N^2) 的时间，运行慢且表的大小必须事先已知。因此当需要具有插入和删除操作时，通常不使用简单数组来实现。

1.2.2 链表实现

为了避免插入和删除的线性开销，我们需要允许表可以不连续存储，否则表的部分或全部需要整体移动。因此，这种情况下更好的实现方式是链表(linked list)。

链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构的指针。我们称之为Next指针。最后一个单元的Next指针指向Null。链表分为：单链表，双链表，循环链表。

链表的 C 语言实现：

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
82
83
84
85
86
#include <stdlib.h>

struct Node
{
    int Element;
    Node* Next;
};

int
IsEmpty(Node* L)
{
    return L->Next == NULL;
}

int
IsLast(Node* P, Node* L)
{
    return P->Next == NULL;
}

Node*
Find(int x, Node* L)
{
    Node* P;
    P = L->Next;
    while(P != NULL && P->Element != x)
        P = P->Next;
    return P;
}

Node*
FindPrevious(int x, Node* L)
{
    Node* P;
    
    P = L;
    while(P->Next != NULL && P->Next->Element != x)
        P = P->Next;
    
    return P;
}

void
Delete(int x, Node* L)
{
    Node* P;
    Node* TmpCell;
    
    P = FindPrevious(x, L);
    
    if (!IsLast(P, L)) {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

void
Insert(int x, Node* L, Node* P)
{
    Node* TmpCell;
    
    TmpCell = (Node*)malloc(sizeof(struct Node));
    
    if (TmpCell != NULL)
        printf("Out of space!!!");
    
    TmpCell->Element = x;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

void
DeleteList(Node* L)
{
    Node* P;
    Node* Tmp;
    P = L->Next;
    L->Next = NULL;
    while(P != NULL)
    {
        Tmp = P->Next;
        free(P);
        P = Tmp;
    }
}

1.2 栈ADT

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶（top）。对栈的基本操作有Push(进栈)和Pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。最后插入的元素可以通过使用Top操作在执行Pop之前读取。

由于栈是一个表，因此任何实现表的方法都能实现栈。通常使用数组是一个较为简便的方法。

1.3 队列ADT

和栈一样，队列（queue）也是表。不同的是，使用队列时插入在一端进行而删除则在另一端进行。

队列的基本操作是Enqueue (入队)，它是在表的末端（rear 队尾）插入一个元素，还有 Dequeue （出队），它是删除（或返回）在表的开头（front 对头）的元素。

2. 树

2.1 基础知识

对于大量的输入数据，链表的线性访问时间太慢，不宜使用。而“树”大部分操作的运行时间平均为 O(log N) 。

一课树是 N 个节点 N-1 条边的集合，其中的一个节点叫做根。

路径

从节点 n_1 到 n_k 的路径（path）定义为节点 n_1, n_2, …, n_k 的一个序列，使得对于 1 \le i < k ,节点 n_i 是 n_{i+1} 的父亲。这个路径的长（length）为该路径上的边的条数，即 k-1 。从每一个节点到它自己都有一条长为 0 的路径。从根到每个节点有且仅有一条路径。

深度

对于任意节点 n_i ， n_i 的深度（depth）为从根到 n_i 的唯一路径的长。因此，根的深度为 0 。

高度

n_i 的高（height）是从 n_i 到一片树叶的最长路径的长。因此，所有树叶的高度都是 0 。

祖先（ancestor）和后裔（descendant）

如果存在从 n_1 到 n_2 的一条路径，那么 n_1 是 n_2 的一位祖先而 n_2 是 n_1 的一个后裔。如果 n_1 \ne n_2 ，那么 n_1 是 n_2 的一位真祖先（proper ancestor）而 n_2 是 n_1 的一个真后裔（proper descendant）。

2.2 树的实现

将每个节点的所有儿子都放在树节点的链表中。FirstChild 是指向第一个儿子的指针，NextSibling 指向下一个兄弟节点。

1
2
3
4
5
6
7
8
typedef struct TreeNode *PtrToNode;

struct TreeNode
{
    ElementType Element;
    PtrToNode FirstChild;
    PtrToNode NextSibling;
}

2.3 树的遍历

先序遍历（preorder traversal）

在先序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前进行的。例如：打印目录树形结构图，先打印父节点，再递归打印子节点。

后序遍历（postorder traversal）

在后序遍历中，在一个节点处的工作是在它的诸儿子节点被计算后进行的。例如：计算目录所占磁盘空间，在得到父节点占用空间前，需要先递归计算子节点所占用的磁盘空间，最后才能逐级向上得到根节点的磁盘总占用空间。

中序遍历（inorder traversal）

用于二叉树。遍历顺序：左子树，节点，右子树。

2.4 二叉树（binary tree）

在二叉树中，每个节点最多只有两个儿子。

二叉树的平均深度为 O(\sqrt{N}) ，而对于特殊类型的二叉树，如二叉查找树（binary search tree）,其平均深度是 O(log N) 。

2.4.1 二叉树实现

因为一棵二叉树最多有两个儿子，所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明。在声明中，一个节点就是由Key信息加上两个指向其他节点的指针（Left 和 　Right）组成的结构。

1
2
3
4
5
6
7
8
9
typedef struct TreeNode *PtrToNode;
typedef struct PtrToNode Tree;

struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
}

二叉树有许多与搜索无关的重要应用。二叉树的主要用处之一是在编译器的设计领域。如二元表达式树。

2.4.2 查找树ADT——二叉查找树

二叉树的一个重要的应用是它们在查找中的使用。使二叉树成为二叉查找树的性质是，对于树中的每个节点 X ，它的左子树所有关键字的值小于 X ，而它右子树中所有关键字值大于 X 的关键字值。

操作集合：

  • MakeEmpty
  • Find
  • FindMin 和 FindMax
  • Insert
  • Delete

2.4.3 AVL 树

AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持，而且它必须保证树的深度是 O(log N) 。最简单的想法是要求左右子树具有相同的高度。另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。虽然这种平衡条件保证了树的深度小，但是它太严格，难以使用，需要放宽条件。

一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

单旋转

双旋转

2.4.4 伸展树（splay tree）

伸展树保证从空树开始任意连续 M 次对树的操作最多花费 O(M log N) 的时间。

2.5 B-树

虽然迄今为止我们所看到的查找树都是二叉树，但是还有一种常用的查找树不是二叉树。这种树叫做B-树（B-tree）。

阶为 M 的B-树是一棵具有下列结构特性的树：

  • 树的根或者是一片树叶，或者其儿子数在2和M之间。
  • 除根外，所有非树叶节点的儿子数在[ M/2 ]和 M 之间。
  • 所有的树叶都在相同的深度上。

B-树实际用于数据库系统，在那里树被存储在物理的磁盘上而不是主存中。一般来说，对磁盘的访问要比任何的主存操作慢几个数量级。如果我们使用M阶B-树，那么磁盘访问的次数是 O(log_{M}N)

3. 散列

散列表的实现常常叫做散列（hashing）。散列是一种用于以常数平均时间执行插入，删除和查找的技术。但是，那些需要元素间任何排序信息的操作将不会得到有效的支持。因此，诸如 FindMin，FindMax 以及以线性时间按排序顺序将整个表进行打印的操作都是散列所不支持的。

3.1 一般想法

理想的散列表数据结构只不过是一个包含关键字（key）的具有固定大小的数组。典型情况下，一个关键字就是一个带有相关值（例如工资信息）的字符串。我们把表的大小记作Table-Size，并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量。通常的习惯是让表从0到Table-Size - 1变化。

每个关键字被映射到从0到Table-Size - 1这个范围中的某个数，并且被放到适当的单元中。这个映射就叫做散列函数（hash function）。理想情况下它应该运算简单并且应该保证任何两个不同的关键字映射到不同的单元。不过，这是不可能的，因为单元的数目是有限的，而关键字实际上是用不完的。因此，我们寻找一个散列函数，该函数要在单元之间均匀地分配关键字。这就是散列的基本想法。剩下的问题则是选择一个函数，决定当两个关键字散列到同一个值的时候（称为冲突collision）应该做什么以及如何确定散列表的大小。

3.2 散列函数

3.2.1 输入整数关键字

如果输入的关键字是整数，则一般合理的方法就是直接返回“Key mod TableSize”（关键字对表大小取模）的结果，除非Key碰巧具有某些不理想的性质。例如，若表的大小是10，而关键字都以0为个位，这意味所有关键字取模运算的结果都是0（都能被10整除）。这种情况，好的办法通常是保证表的大小是素数（也叫质数，只能被1和自身整除）。当输入的关键字是随机的整数时，散列函数不仅算起来简单而且关键字的分配也很均匀。

3.2.2 输入字符串关键字

通常，关键字是字符串；在这种情形下，散列函数需要仔细地选择。

一种方法是把字符串中字符的ASCII码值加起来。以下该方法的C语言实现。

1
2
3
4
5
6
7
8
9
10
typedef unsigned int Index;

Index
Hash(const char *Key, int TableSize)
{
    unsigned int HashVal = 0;
    while(*Key != '\0')
        HashVal += *Key++;
    return HashVal % TableSize;
}

这种方法实现起来简单而且能很快地计算出答案。不过，如果表很大，则函数将不会很好地分配关键字。例如，设 TableSize = 10007 （10007是素数），并设所有的关键字至多8个字符长。由于char型量的值最多是127，因此散列函数只能取在0和1016之间，其中 1016=127\times8 。这显然不是一种均匀分配。

第二种方法。假设Key至少有两个字符外加NULL结束符。值27表示英文字母表的字母个数外加一个空格，而 729=27^2 。该函数只考查前三个字符，假如它们是随机的，而表的大小像前面那样还是10007，那么我们就会得到一个合理的均衡分配。

1
2
3
4
5
Index
Hash(const char *Key, int TableSize)
{
    return (Key[0] + 27*Key[1] + 729*Key[2]) % TableSize;
}

可是不巧的是，英文并不是随机的。虽然3个字符（忽略空格）有 26^3 = 17576 种可能组合，但查验词汇量足够大的联机词典却揭示：3个字母的不同组合数实际只有2851。即使这些组合没有冲突，也不过只有表的28%被真正散列到。因此，虽然很容易计算，但是当散列表足够大的时候这个函数还是不合适的。

一个更好的散列函数。这个散列函数涉及到关键字中的所有字符，并且一般可以分布得很好。计算公式如下：

\sum_{i=0}^{KeySize-1} Key[KeySize-1-i]\cdot32^i

它根据Horner法则计算一个（32的）多项式。例如，计算 h_k=k_1 + 27k_2 + 27^2k_3 的另一种方式是借助于公式 h_k=(k_3 \times 27 + k_2)\times 27 + k_1 进行。Horner法则将其扩展到用于 n 次多项式。

1
2
3
4
5
6
7
8
9
Index
Hash(const char *Key, int TableSize)
{
    unsigned int HashVal = 0;

    while(*Key != '\0')                     /* 1 */
        HashVal = (HashVal << 5) + *Key++;  /* 2 */
    return HashVal % TableSize;             /* 3 */
}

这里之所以用 32 替代27，是因为用32作乘法不是真的去乘，而是移动二进制的5位。为了运算更快，程序第2行的加法可以用按位异或来代替。虽然就表的分布而言未必是最好的，但确实具有及其简单的优点。如果关键字特别长，那么该散列函数计算起来将会花费过多的时间，不仅如此，前面的字符还会左移出最终的结果。这种情况，通常的做法是不使用所有字符。此时关键字的长度和性质将影响选择。

3.3 冲突解决

解决了关键字均匀映射的问题，剩下的主要编程细节是解决冲突的消除问题。如果当一个元素被插入时另一个元素已经存在（散列值相同），那么就产生了冲突，这种冲突需要消除。解决这种冲突的方法有几种。最简单的两种是：分离链接法和开放定址法。

3.3.1 分离链接法（separate chaining）

分离链接法是将散列到同一个值的所有元素保留到一个表中。为了方便起见，这些表都有表头，实现方法与表ADT相同。如果空间很紧，则更可取的方法是避免使用这些表头。

类型声明：

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
#ifndef _HashSep_H

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);

ElementType Retrieve(Position P);

#endif

struct ListNode
{
    ElementType Element;
    Position Next;
};

typedef Position List;

struct HashTbl
{
    int TableSize;
    List *TheLists;
};

初始化函数：

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
HashTable
InitializeTable(int TableSize)
{
    HashTable H;
    int i;

    if (TableSize < MinTableSize)
    {
        Error("Table size too small");
        return NULL;
    }

    H = malloc(sizeof(struct HashTbl));
    if (H == NULL)
        FatalError("out of space!!!");

    H->TableSize = NextPrime(TableSize);                /* 1 设置素数大小 */
    H->TheLists = malloc(sizeof(List) * H->TableSize);  /* 2 */
    if (H->TheLists == NULL)
        FatalError("Out of space!!!");
    
    /**
      * 分配链表表头
      * 
      * 给每一个表设置一个表头，并将 Next 指向 NULL。如果不用表头，以下代码可省略。
      */
    for(i = 0; i < H->TableSize; i++)
    {
        H->TheLists[i] = malloc(sizeof(struct ListNode)); /* 3 */
        if (H->TheLists[i] == NULL)
            FatalError("Out of space!!!");
        else
            H->TheLists[i]->Next = NULL;
    }

    return H;
}

以上程序低效之处是标记为3处malloc执行了H->TableSize次。这可以通过循环开始之前调用一次malloc操作：

1
H->TheLists = malloc(sizeof(struct ListNode) * H->TableSize);

Find 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
Position
Find(ElementType Key, HashTable H)
{
    Position P;
    List L;

    L = H->TheLists[ Hash(Key, H->TableSize) ];
    P = L->Next;
    while(P != NULL && P->Element != Key)   /* ElementType 为 int时比较。字符串比较使用 `strcmp` */
        P = P->Next;

    return P;
}

注意，判断 P->Element != Key，这里适用于整数。字符串比较用 strcmp 替换。

Insert 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void
Insert(ElementType Key, HashTable H)
{
    Position Pos, NewCell;
    List L;

    Pos = Find(Key, H);
    if (Pos == NULL)
    {
        NewCell = malloc(sizeof(struct ListNode));
        if(NewCell == NULL)
            FatalError("Out of space!!!");
        else
        {
            L = H->TheLists[ Hash(Key, H->TableSize) ];
            NewCell->Next = L->Next;
            NewCell->Element = Key;
            L->Next = NewCell;
        }
    }
}

如果在散列中诸例程中不包括删除操作，那么最好不要使用表头。因为这不仅不能简化问题而且还要浪费大量的空间。

3.3.2 开放定址法（Open addressing hashing）

类型声明：

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
#ifndef _HashQuad_H

typedef unsigned int Index;
typedef Index Position;

struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, HashTable H);
ElementType Retrieve(Position P, HashTable H);
HashTable Rehash(HashTable H);

#endif

enum KindOfEntry { Legitimate, Empty, Deleted };

struct HashEntry
{
    ElementType Element;
    enum KindOfEntry Info;
};

typedef struct HashEntry Cell;

struct HashTbl
{
    int TableSize;
    Cell *TheCells;
};

初始化开放定址散列表:

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
HashTable
InitializeTable(int TableSize)
{
    HashTable H;
    int i;

    if (TableSize < MinTableSize)
    {
        Error("Table size too small");
        return NULL;
    }

    /* 给散列表分配内存 */
    H = malloc(sizeof(struct HashTbl));
    if (H == NULL)
        FatalError(Out of space!!!);
    
    H->TableSize = NextPrime(TableSize);    /* 大于 TableSize 的第一个素数 */

    /* 给数组所有单元分配内存 */
    H->TheCells = malloc(sizeof(Cell) * H->TableSize);
    if(H->TheCells == NULL)
        FatalError("Out of space!!!");
    
    for (i = 0; i < H->TableSize; i++)
        H->TheCells[i].Info = Empty;

    return H;
}

Find 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Position
Find(ElementType Key, HashTbl H)
{
    Position CurrentPos;
    int CollisionNum;

    CollisionNum = 0;
    CurrentPos = Hash(Key, H->TableSize);
    while(H->TheCells[CurrentPos].Info != Empty &&
          H->TheCells[CurrentPos].Element != Key)
          /* 这里可能需要使用 strcmp 字符串比较函数 !! */
    {
        CurrentPos += 2 * ++CollisionNum - 1;
        if (CurrentPos >= H->TableSize)
            CurrentPos -= H->TableSize;
    }

    return CurrentPos;
}

Insert 操作：

1
2
3
4
5
6
7
8
9
10
void Insert(ElementType Key, HashTable H)
{
    Position Pos;
    Pos = Find(Keu, H);
    if (H->TheCells[Pos].Info != Legitimate)
    {
        H->TheCells[Pos].Info = Legitimate;
        H->TheCells[Pos].Element = Key; /* 字符串类型需要使用 strcpy 函数 */
    }
}

3.4 散列表的应用

散列有着丰富的应用。编译器使用散列表跟踪源代码中声明的变量。这种数据结构叫做符号表(symbol table)。散列表是这种问题的理想应用，因为只有Insert和Find操作。标识符一般都不长，因此其散列函数能够迅速被算出。

散列表常见的用途也出现在为游戏编写的程序中。当程序搜索游戏的不同的行时，它跟踪通过计算机基于位置的散列函数而看到的一些位置。如果同样的位置再出现，程序通常通过简单移动变换来避免昂贵的重复计算。游戏程序的这种一般特点叫做变换表(transposition table)。

另外一个用途是在线拼写检验程序。如果错拼检测（与纠正错误相比）更重要，那么整个词典可以被预先散列，单词则可以在常数时间内被检测。散列表很适合这项工作，因为以字母顺序排列单词并不重要；而以它们在文件中出现的顺序显示出错误拼写当然是可以接受的。

4. 优先队列（堆）

4.1 为什么需要优先队列？

队列是一种先进先出的表ADT，正常来说，先入队的元素，会先出队，意味没有那个元素是特殊的，拥有“插队”的优先权。这种平等，并不试用所有场景。有时，我们希望队列中某类元素拥有比其他元素更高的优先级，以便能提前得到处理。因此，我们需要有一种新的队列来满足这样的应用，这样的队列叫做“优先队列（priority queue）”。

4.2 优先队列模型

优先队列允许至少两种操作：Insert(插入) ，以及 DeleteMin(删除最小者)。Insert 操作等价于 Enqueue(入队)，而 DeleteMin 则是队列中 Dequeue(出队) 在优先队列中的等价操作。DeleteMin 函数也变更它的输入。

4.3 简单实现

4.3.1 单链表实现

在表头以 O(1) 执行插入操作，并遍历该链表以删除最小元，这又需要 O(N) 时间。另一种做法是，始终让表保持排序状态；这使得插入代价高昂（ O(N) ）而DeleteMin花费低廉（ O(1) ）。基于DeleteMin的操作次数从不多于插入操作次数的事实，前者也许是更好的办法。

4.3.2 二叉查找树实现

使用二叉查找树，Insert 和 DeleteMin 这两种操作的平均运行时间都是 O(log N) 。

4.4 二叉堆（binary heap）

实现优先队列更加普遍的方法是二叉堆，以至于当堆(heap)这个词不加修饰地使用时一般都是指该数据结构(优先队列)的这种实现。因此，我们单独说堆时，就是指二叉堆。同二叉查找树一样，堆也有两个性质，即结构性和堆序性。正如AVL树一样，对堆的一次操作可能破坏这两个性质的一个，因此，堆的操作必须要到堆的所有性质都被满足时才能终止。事实上这并不难做到。

4.4.1 结构性质

堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树（complete binary tree）。因为完全二叉树很有规律，所以它可以用一个数组表示而不需要指针。对于数组任意位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 2i+1 上，它的父亲则在位置 \lfloor i/2 \rfloor 上。因此，不仅指针这里不需要，而且遍历该树所需要的操作也极简单，在大部分计算机上运行很可能非常快。

一个堆数据结构由一个数组，一个代表最大值的整数以及当前的堆大小组成。

优先队列声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef _BinHeap_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);

#endif

struct HeapStruct
{
    int Capacity;
    int Size;
    ElementType *Elements;
}

4.4.2 堆序性质

使操作被快速执行的性质是堆序(heap order)性。由于我们想要快速地找出最小元，因此，最小元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于它的所有后裔。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PriorityQueue
Initialize(int MaxElements)
{
    PriorityQueue H;

    if (MaxElements < MinPQSize)
        Error("Priority queue size is too small");
    
    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL)
        FatalError("Out of space!!!");
    
    H->Elements = malloc((MaxElements + 1)
                         * sizeof(ElementType));
    
    if (H->Elements == NULL)
        FatalError("Out of space!!!");

    H->Capacity =  MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;

    return H;
}

根据堆序性质，最小元总是可以在根处找到。因此，我们以常数时间完成附加运算FinMin。

4.5 堆的基本操作

4.5.1 Insert (插入)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void
Insert(ElementType X, PriorityQueue H)
{
    int i;

    if (IsFull(H))
    {
        Error("Priority queue is full");
        return;
    }
    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}

4.5.2 DeleteMin (删除最小元)

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
ElementType
DeleteMin(PriorityQueue H)
{
    int i, Child;
    ElementType MinElement, LastElement;

    if (IsEmpty(H))
    {
        Error("Priority queue is empty");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for(i = 1; i * 2 <= H->Size; i = Child)
    {
        Child = i * 2;
        if (Child != H->size && H->Elements[Child + 1]
                              < H->Elements[Child])
            Child++;

        if (LastElement > H->Elements[ Child ])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

4.6 优先队列的应用

  • 操作系统设计：进程调度
  • 图论算法
  • 选择问题：从N个元素中找出第k个最大的元素
  • 事件模拟
青笔 wechat
我是一条小青蛇 我有很多小秘密
  • 本文作者： 青笔
  • 本文链接： http://www.qingbii.com/2019/11/01/adt/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！