Understanding Heaps in Binary Trees
Heaps are binary trees that adhere to specific properties, such as being complete and satisfying the heap-order property. This involves nodes having keys smaller than or equal to their children. Key operations like removeMin and insert can be performed on heaps efficiently. Array implementations allow for easy manipulation of heap structures. Transforming a complete binary tree into a heap involves converting subtrees into heaps, following a specific buildHeap algorithm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Heaps A heap is a binary tree that satisfies the following properties: Structure property: It is a complete binary tree Heap-order property: Each node satisfies the heap condition: The key of every node must be smaller than (or equal to) the keys of its children, i.e. n.info n.left.info and n.info n.right.info, for all nodes n Note: this is called a min-heap max-heaps have the opposite heap condition. COSC 2P03 Week 6 1
removeMin Algorithm min-heap temp = root; root = last node; current = root; while current has at least 1 child { smaller = smallest child; if (current < smaller) break; else swap(current, smaller); } return temp; What is the complexity? COSC 2P03 Week 6 2
insert Algorithm min-heap put new node at bottom right of tree and call it current; // trickle up while key of current < key of its parent swap (current, parent); What is the complexity? COSC 2P03 Week 6 3
Array implementation of Heap array[0..capacity]: the heap array array[1..currentsize]: elements currently in heap currentsize: number of nodes in heap removeMin (see fig. 6.12 for full details): The smallest element is the root, which is array[1] The last element (rightmost on lowest level) is array[currentsize] In trickle-down, we need to find the children of a node: Left child of array[t] is array[2t] Right child of array[t] is array[2t+1] COSC 2P03 Week 6 4
Array implementation of Heap removeMin Example 0 1 2 3 4 5 6 7 5 35 10 50 60 40 20 0 1 2 3 4 5 6 20 35 10 50 60 40 0 1 2 3 4 5 6 10 35 20 50 60 40 COSC 2P03 Week 6 5
Array implementation of Heap (insert see fig. 6.8 for full details) Insert in array[currentsize+1] During trickle-up, we need to find the parent of a node: Parent of array[t] is array[ t/2 ] Example: insert 15 7 0 1 2 3 4 5 6 15 10 35 20 50 60 40 3 7 0 1 2 4 5 6 15 20 10 35 50 60 40 COSC 2P03 Week 6 6
Transforming a complete binary tree into a heap In a heap, all subtrees are also heaps. Idea: transform all subtrees into heaps, starting from smallest. Note that leaves are already heaps. Note:array[ currentsize/2 ]is the parent of the last node in the heap. buildHeapalgorithm: for (i = currentsize/2 ; i >= 1; i--) apply trickle-down to array[i]; COSC 2P03 Week 6 7
buildHeap example 41 i=5 59 36 58 21 97 31 16 26 53 21 i=4 59 36 58 41 97 31 16 26 53 58 i=3 59 36 16 41 97 31 21 26 53 36 i=2 59 31 16 41 97 58 21 26 53 59 i=1 16 31 21 41 97 58 36 26 53 End 16 21 31 26 41 97 58 36 59 53 COSC 2P03 Week 6 8
Heapsort version 1 min heap The results are stored in B[1..n]. buildHeap(A); for(i = 1; i <= n; i++) B[i] = removeMin(A); 16 21 31 26 41 97 58 36 59 53 B[1] = 16 21 26 31 36 41 97 58 53 59 B[2] = 21 (etc) COSC 2P03 Week 6 9
Heapsort version 2 max heap Better idea: avoid the use of a second array by storing sorted elements at the end of the array Use a max-heap: At each step, swap root with last element, then apply trickle down to new root Example after conversion to max heap: 97 53 59 26 41 58 31 16 21 36 After 1st swap: 59 53 58 26 41 36 31 16 21 97 After 2nd swap: 58 53 36 26 41 21 31 16 59 97 COSC 2P03 Week 6 10
