浙江大学陈越（ppt课件）.ppt

浙江大学 陈 越
*
—— 按照元素的优先权（关键字大小）出队
重要操作：
入队 – Insert
出队 – DeleteMin / DeleteMax
*
 数组 :
插入 — 元素总是插入尾部 ~  ( 1 )
删除 — 查找最大（或最小）关键字 ~  ( n )
从数组中删去需要移动元素 ~ O( n )
 链表:
插入 — 元素总是插入链表的头部 ~  ( 1 )
删除 — 查找最大（或最小）关键字 ~  ( n )
删去结点 ~ ( 1 )
 有序数组:
插入 — 找到合适的位置 ~ O( n ) 或 O(log2 n )
移动元素并插入 ~ O( n )
删除 — 删去最后一个元素 ~ ( 1 )
 有序链表:
插入 — 找到合适的位置 ~ O( n )
插入元素 ~ ( 1 )
删除 — 删除首元素或最后元素 ~ ( 1 )
*
二叉搜索树？
可以，但没必要……
我们其实需要：
一棵平衡的树
容易找到最大/最小值
*
4
8
9
5
10
11
6
12
13
7
14
15
2
3
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
…
A
B
C
D
E
F
G
H
I
J
D
H
I
E
J
F
G
B
C
A
i 的父结点序号是 i/2；
左孩子序号是 2i；
右孩子序号是 2i+1.
*
任一结点的值比其所有子结点（如果有的话）的值都要大/小。
90
87
5
64
12
79
2
55
9
12
68
43
最大树
1
46
95
8
51
62
98
72
25
13
70
86
最小树
*
最大/最小完全二叉树
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
ElementType *Data; /* 存储元素的数组 */
int Size; /* 堆中当前元素个数 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */
*
MaxHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */
MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
H->Data = (ElementType *)
malloc((MaxSize+1)*sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MAXDATA; /*定义"哨兵"为大于堆中所有可能元素的值*/
return H;
}
*
10
12
15
20
[1]
[2]
[3]
[4]
18
[5]
[6]
新结点 = 21
21
20
21
<
新结点 = 17
17
20
17
>
17
20
10
17
<
新结点 = 9
20
9
>
9
10
9
>
9
10
唯一允许增加的结点，
因为必须保持一棵完全二叉树。