Heaps and Priority Queues PDF

IT1815 Heaps and Priority Queues or remove(). The dequeue operation starts with the minimum Heaps element. A heap is a complete binary tree where the value of eac...

IT1815 Heaps and Priority Queues or remove(). The dequeue operation starts with the minimum Heaps element. A heap is a complete binary tree where the value of each of Sample code to dequeue in Java based on natural order: each parent node is either higher or lower than the value of its PriorityQueue printer = new PriorityQueue(); child nodes. printer.add(9); These are the two (2) types of heap: printer.add(7); o Min Heap – The value of each parent node is less printer.add(1); printer.add(3); than or equal to the values of its child nodes. while (!printer.isEmpty()) { o Max Heap – The value of each parent node is greater System.out.print(printer.remove() + " "); than or equal to the values of its child nodes. } Output: 1 3 7 9 Sample code to dequeue in Python based on natural order: from queue import PriorityQueue prio = PriorityQueue() prio.put("dog") prio.put("d") Min Heap Max Heap prio.put("dogs") Heaps can be implemented in Java using ArrayList from the while not prio.empty(): java.util package. next_item = prio.get() Example: print(next_item) ArrayList heap = new ArrayList(); A comparator is used to create a specific ordering for a To create a heap with initial values, use the addAll() method collection of objects. of the Collections class (also from the java.util package). To create a comparator in Java, use the Comparator interface Example (based on the given min heap above): ArrayList minHeap = new ArrayList(); and its methods such as comparing(), comparingInt(), Collections.addAll(minHeap, 1, 7, 6, 8, 9); and compare(). Explanation: The root node is always at index 0. Its child Sample code to dequeue in Java based on a custom order: Comparator comp = Comparator.comparing(String::length); nodes are always at index 1 and index 2. Indices 3, 4, 5, and //:: indicates a method reference, ContainingType::methodName 6 can store the child nodes of those two (2) nodes and so on. PriorityQueue prio = new PriorityQueue(comp); To determine the root node, use the get() method. prio.add("cat"); Example: System.out.print(minHeap.get(0)); prio.add("c"); prio.add("cats"); while (!prio.isEmpty()) { Priority Queues System.out.println(prio.remove()); A priority queue is a special type of queue where elements } are processed based on their order (natural or custom). References: Koffman, E. & Wolfgang, P. (2016). Data structures: Abstraction and design using Java. Priority queues can be implemented in Java using the Hoboken: John Wiley & Sons, Inc. PriorityQueue class from the java.util package. Oracle Docs. (n.d.). Citing sources. Retrieved from Example: https://docs.oracle.com/javase/8/docs/api/java/util/package-summary.html PriorityQueue printer = new PriorityQueue(); Python Software Foundation. (n.d.). The Python tutorial. Retrieved from https://docs.python.org/3/tutorial/index.html To enqueue, use add() or offer(). To dequeue, use poll() 07 Handout 1 *Property of STI  [email protected] Page 1 of 1