Chapter 25 - Heaps and priority queues. This chapter completes our tour of data structures. After you have mastered the material in this chapter, you will be able to: Learn about heaps, review the class, learn about heapsort. | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Heaps and Priority Queues 2 H C R E A 5 T P 25- This chapter completes our tour of data structures. Objectives: Learn about heaps Review the class Learn about Heapsort 25- Heap algorithms are simple and elegant. Priority Queues A priority queue is a data structure for temporary storage that delivers the stored items in order of their priority: an item with higher priority is delivered first. The objects in a priority queue are Comparable (or a comparator is provided). According to convention, the smaller item has higher priority. 25- A priority queue can hold duplicate objects. Instead of using comparable objects, we could use items with some method defined that returns the item’s priority. If priority can take only a small number of discrete values (for example, 0 | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Heaps and Priority Queues 2 H C R E A 5 T P 25- This chapter completes our tour of data structures. Objectives: Learn about heaps Review the class Learn about Heapsort 25- Heap algorithms are simple and elegant. Priority Queues A priority queue is a data structure for temporary storage that delivers the stored items in order of their priority: an item with higher priority is delivered first. The objects in a priority queue are Comparable (or a comparator is provided). According to convention, the smaller item has higher priority. 25- A priority queue can hold duplicate objects. Instead of using comparable objects, we could use items with some method defined that returns the item’s priority. If priority can take only a small number of discrete values (for example, 0 - 9), we can use a mechanism similar to a lookup table, arranging the items in order of their priority (for example, an array of FIFO queues, each queue for objects of a particular priority). Possible Implementations A sorted list: items are stored in order of priority remove and peek are O(1), but add is O(n). An unsorted list: items are stored in order of their arrival add is O(1) but remove and peek are O(n). Either way, one of the methods creates a bottleneck. 25- As usual, a divide-and-conquer type of structure helps overcome this bottleneck. Heaps A heap is a particular kind of a binary tree. Heaps provide a way to implement priority queues in such a way that both add and remove take O(log n) time. A heap can be stored in an array (or in an ArrayList). 25- And peek takes O(1) time. Full and Complete Binary Trees Full tree: all levels are filled; a full tree with h levels holds 2h - 1 nodes. Complete tree: all levels are filled, except perhaps the bottom one
