1、数据数据 结结 构构Data Structure第六章第六章 优先级队列优先级队列第六章第六章 优先级队列优先级队列n 基本的优先级队列 n 二叉堆 n D堆 n 归并优先级队列 n STL中的优先级队列 n 排队系统的模拟基本的优先级队列基本的优先级队列n 结点之间的关系是由结点的优先级决定的，而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队。这样的队列称为优先级队列。 Priority queuen Collections. Insert and delete items. Which item to delete?n Stack. Remove the item most
2、recently added.n Queue. Remove the item least recently added.n Randomized queue. Remove a random item.n Priority queue. Remove the largest (or smallest) item.Priority queue applicationsn Event-driven simulation. customers in a line, colliding particlesn Numerical computation. reducing round off erro
3、rn Data compression. Huffman codesn Graph searching. Dijkstras algorithm, Prims algorithmn Number theory. sum of powersn Artificial intelligence. A* searchn Statistics. maintain largest M values in a sequencen Operating systems. load balancing, interrupt handlingn Discrete optimization. bin packing,
4、 schedulingn Spam filtering. Bayesian spam filterChallenge. Find the largest M files in N itemsConstraint. Not enough memory to store N items优先级队列的简单实现优先级队列的简单实现n 利用现有的队列结构。有两种方法可以处理优先级 n 入队时，按照优先级在队列中寻找合适的位置， 将新入队的元素插入在此位置。出队操作的实现保持不变。入队操作的时间复杂度是 O （ N），出队操作的时间复杂度是 O（ 1）。 n 入队操作的实现保持不变，将新入队的元素放在 队列
5、尾。但出队时，在整个队列中查找优先级最高的元素，让它出队。入队操作的时间复杂度是 O （ 1），出队操作的时间复杂度是 O（ N）。第六章第六章 优先级队列优先级队列n 基本的优先级队列 n 基于树形结构的优先级队列 二叉堆 n D堆 n 归并优先级队列 n STL中的优先级队列 n 排队系统的模拟48 9510 11612 13714 152 31A complete binary tree of height h has betweenand nodes.2h-12h 1 h = log N +1 Array Representation : BT n + 1 ( BT 0 is not
6、used)DH IEJF GB CABT 0 1A 2B 3C 4D 5E 6F7G8H9I10J11 12 13完全二叉树完全二叉树定 义 ： A binary tree with n nodes and height h is complete iff its nodes correspond to the nodes numbered from 1 to n in the perfect binary tree of height h.【 定理 】 If a complete binary tree with n nodes is represented sequentially, then for any node with index i, 1 i n, we have:自然界的完全二叉树自然界的完全二叉树
