TreeNote2 - juedaiyuer/researchNote GitHub Wiki

#堆#

优先队列

优先队列(Priority Queue),取出元素的顺序依照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序

##优先队列的实现##

数组实现

1. 插入-总是插入尾部
2. 删除-查找最大或者最小关键字；从数组中删除需要移动的元素

链表实现

1. 元素总是插入链表的头部
2. 查找最大或最小关键字；删去结点

有序数组

1. 插入-找到合适的位置；移动元素并插入
2. 删除-删去最后一个元素

有序链表

1. 插入-找到合适的位置；插入元素
2. 删除-删除首元素或最后元素

二叉树存储结构

堆的特点:使用完全二叉树来进行数据的存储
最大堆:根结点要比左右结点要大
最小堆:...要小
从根结点到任意结点路径上结点序列的有序性

##哈夫曼树与哈夫曼编码##

带权路径长度(WPL)
最优二叉树或哈夫曼树:WPL最小的二叉树

哈夫曼树的构造
1.每次把权值最小的两颗二叉树合并