(See related pages)
|
|
|
| This chapter introduced the priority queue: a collection in which removal is allowed
only of the highest-priority element in the sequence, according to some method for
comparing elements. The PurePriorityQueue interface may be implemented in a variety
of ways. The most widely used implementation is the Heap class. A heap t is a
complete binary tree such that either t is empty or
1. The root element of t is smallest element in t, according to some method for
comparing elements. 2. The left and right subtrees of t are heaps. Because array-based representations of complete binary trees allow rapid calculation of a parent’s index from a child’s index and vice versa, the heap can be implemented as an array or ArrayList. This utilizes an array’s ability to randomly access the element at a given index. The heapSort method is a fast sort that creates a heap from a list, clears the list, and then repeatedly removes the smallest element in the heap and appends it to the list. The application of priority queues was in the area of data compression. Given a message, it is possible to encode each character, unambiguously, into a minimum number of bits. One way to achieve such a minimum encoding is with a Huffman tree. A Huffman tree is a two-tree in which each leaf represents a distinct character in the original message, each left branch is labeled with a 0, and each right branch is labeled with a 1. The Huffman code for each character is constructed by tracing the path from that leaf character back to root, and prepending each branch label in the path. |