CMPT225 Final Review 2. Simon Fraser University CMPT 225

CMPT225 Final Review - MT 后

ppt22 Binary Heap ADT class
ppt23 Priority Queue ADT class
ppt26 Binary heap sort (见 MT 前 Sorting)
ppt27-31 Hashing ADT class, Collision resolution strategies
ppt32 Dictionary ADT class
ppt33-34 Disk-bound data
ppt34-36 Merge sort (见 MT 前 Sorting), B-tree external ADT class




ADT Binary Heap Priority Queue Hashing Dictionary
Array: unsorted/ sorted
Array: unsorted/ sorted
LL: unsorted/ sorted
LL: unsorted/ sorted Array,
CDT Array BST ADT class
BST ADT class Array+LL
AVL ADT class
Binary Heap ADT class: max/ min
Hashing ADT class

,ppt22
1. Binary Heap ADT class:
(1) 定义:
 是 complete binary tree (除最下层的结点可以不连满, 其它层的结点都连满),
且 resulting array 无 gap
 在 complete binary tree 中给结点的计数方式: 逐层数, 从左向右数
 设某结点的 index 为 i:
则其左孩子的 index 为 2*i+1
则其右孩子的 index 为 2*i+2
则其 parent 的 index 为 (i-1)/2 向下取整
所有 index < array capacity
 适用于查找获取最大最小值
 not for general purpose


(2) Max/ Min binary heap:
 Max binary heap: complete binary tree, root 值最大, 左右子树大小无所谓
 Min binary heap: complete binary tree, root 值最小, 左右子树大小无所谓


(3) Operation:
 insert: 加到 index 的下一位, 换位
 remove: 删 root, 最后一位补位, 换位
 retrieve: retrieve root

, Max/ Min binary heap insertion: 加到 index 下一位, 换位