CHAPTER 10
Heaps and Treaps
By Prof. Rafael Orta, M.S.
NOTE: The material in this presentation is a compilation from C++ for Dummies by Stephen Randy Davis and the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
https://quizizz.com/
This week agenda
Heap concept
A Heap is a Binary Tree with following properties.
�1) It’s a complete tree (All levels are filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is like MinHeap.
Heaps
Heap concept
Some applications require fast access to and removal of the maximum item in a changing set of items. For example, a computer may execute jobs one at a time; upon finishing a job, the computer executes the pending job having maximum priority. Ex: Four pending jobs have priorities 22, 14, 98, and 50; the computer should execute 98, then 50, then 22, and finally 14. New jobs may arrive at any time.
Maintaining jobs in fully-sorted order requires more operations than necessary, since only the maximum item is needed. A max-heap is a binary tree that maintains the simple property that a node's key is greater than or equal to the node's children's' keys. (Actually, a max-heap may be any tree, but is commonly a binary tree). Because x ≥ y and y ≥ z implies x ≥ z, the property results in a node's key being greater than or equal to all the node's descendants' keys. Therefore, a max-heap's root always has the maximum key in the entire tree.
Heaps
Max-heap insert and remove operations
An insert into a max-heap starts by inserting the node in the tree's last level, and then swapping the node with its parent until no max-heap property violation occurs. Inserts fill a level (left-to-right) before adding another level, so the tree's height is always the minimum possible. The upward movement of a node in a max-heap is sometime called percolating.
A remove from a max-heap is always a removal of the root and is done by replacing the root with the last level's last node and swapping that node with its greatest child until no max-heap property violation occurs. Because upon completion that node will occupy another node's location (which was swapped upwards), the tree height remains the minimum possible.
Heaps
Heaps – Max-heap Insert and Remove
80 is the greatest child
Heaps using arrays
Heap storage
Heaps are typically stored using arrays. Given a tree representation of a heap, the heap's array form is produced by traversing the tree's levels from left to right and top to bottom. The root node is always the entry at index 0 in the array, the root's left child is the entry at index 1, the root's right child is the entry at index 2, and so on.
Assume we want to add a new value 63
Heap Sort
Heapify operation
Heapsort is a sorting algorithm that takes advantage of a max-heap's properties by repeatedly removing the max and building a sorted array in reverse order. An array of unsorted values must first be converted into a heap. The heapify operation is used to turn an array into a heap. Since leaf nodes already satisfy the max heap property, heapifying to build a max-heap is achieved by percolating down on every non-leaf node in reverse order.
Heap Sort
As you can see the array is not yet sorted. Next, we will see the entire process.
Heap Sort
The array is heapified first. Each internal node is percolated down, from highest node index to lowest.
The end index is initialized to 6, to refer to the last item. 94's "removal" starts by swapping with 68.
Removing from a heap means that the rightmost node on the lowest level disappears before the percolate down. End index is decremented after percolating.
88 is swapped with 49, the last node disappears, and 49 is percolated down.
The process continues until end index is 0.
Heap Sort
The array is heapified first. Each internal node is percolated down, from highest node index to lowest.
Priority Queue Abstract Data Type
Priority queue abstract data type
A priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. The priority queue push operation inserts an item such that the item is closer to the front than all items of lower priority, and closer to the end than all items of equal or higher priority. The priority queue pop operation removes and returns the item at the front of the queue, which has the highest priority.
Common Priority Queue Operations
Implementing Priority Queues with heaps
A priority queue is commonly implemented using a heap. A heap will keep the highest priority item in the root node and allow access in O(1) time. Adding and removing items from the queue will operate in worst-case O(𝑙𝑜𝑔𝑁) time.
Treaps
Treap basics
A BST built from inserts of N nodes having random-ordered keys stays well-balanced and thus has near-minimum height, meaning searches, inserts, and deletes are O(𝑙𝑜𝑔𝑁). Because insertion order may not be controllable, a data structure that somehow randomizes BST insertions is desirable. A treap uses a main key that maintains a binary search tree ordering property, and a secondary key generated randomly (often called "priority") during insertions that maintains a heap property. The combination usually keeps the tree balanced.
Treaps
Treap basics
The word "treap" is a mix of tree and heap. This section assumes the heap is a max-heap. Algorithms for basic treap operations include:
Treaps
Treaps
Treap Delete
A treap delete could be done by first doing a BST delete (copying the successor to the node-to-delete, then deleting the original successor), followed by percolating the node down until the heap property is not violated. However, a simpler approach just sets the node-to-delete's priority to -∞ (for a max-heap), percolates the node down until a leaf, and removes the node. Percolating the node down uses rotations, not swaps, to maintain the BST property. Also, the node is rotated in the direction of the lower-priority child, so that the node rotated up has a higher priority than that child, to keep the heap property.