Heaps and HeapsortHeapsWhat is Heap?Slide 4PowerPoint PresentationSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Heap Storage RulesSlide 13Slide 14Slide 15Slide 16Heap implementation of priority queueAdding a Node to a HeapSlide 19Slide 20Slide 21Removing the Top of a HeapSlide 23Slide 24Slide 25Slide 26Slide 27Adding an Entry to a HeapSlide 29Slide 30Slide 31Adding an entry to a priority queueReheapification upwardImplementing a HeapSlide 35Slide 36Slide 37Slide 38Important Points about the ImplementationSlide 40Removing an entry from a HeapSlide 42Removing an entry from a heapSlide 44HeapsortHeap representationSlide 47Rules for location of data in the arraySlide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Pseudocode for the heapsort algorithmAnalysisSlide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Heaps and HeapsortHeaps and HeapsortProf. Sin-Min LeeDepartment of Computer ScienceSan Jose State University•Heap Definition. •Adding a Node.•Removing a Node.•Array Implementation.•Analysis•Source Code.HeapsHeapsWhat is Heap?A heap is like a binary search tree. It is a binary tree where the six comparison operators form a total order semantics that can be used to compare the node’s entries. But the arrangement of the elements in a heap follows some new rules that are different from a binary search tree.HeapsHeapsA heap is a certain kind of complete binary tree. It is defined by the following properties.Heaps (Priority Queues)A heap is a data structure which supports efficient implementation of three operations: insert, findMin, and deleteMin. (Such a heap is a min-heap, to be more precise.)Two obvious implementations are based on an array (assuming the size n is known) and on a linked list. The comparisons of their relative time complexity are as follows: insert findMin deleteMin Sorted array O(n) O(1) O(1) (from large (to move (find at end) (delete the end) to small) elements)Linked list O(1) O(1) O(n) (append) (a pointer to Min) (reset Min pointer)HeapsHeaps1. All leaf nodes occur at adjacent levels.When a completebinary tree is built,its first node must bethe root.When a completebinary tree is built,its first node must bethe root.RootHeapsHeaps2. All levels of the tree, except for the bottom level are completely filled. All nodes on the bottom level occur as far left as possible.Left childof therootThe second node isalways the left childof the root.The second node isalways the left childof the root.HeapsHeaps3. The key of the root node is greater than or equal to the key of each child. Each subtree is also a heap.Right childof therootThe third node isalways the right childof the root.The third node isalways the right childof the root.HeapsHeapsThe next nodesalways fill the nextlevel from left-to-right..The next nodesalways fill the nextlevel from left-to-right..HeapsHeapsThe next nodesalways fill the nextlevel from left-to-right.The next nodesalways fill the nextlevel from left-to-right.HeapsHeapsComplete binary tree.Heap Storage Rules•A heap is a binary tree where the entries of the nodes can be compared with a total order semantics. In addition, these two rules are followed:•The entry contained by a node is greater than or equal to the entries of the node’s children.•The tree is a complete binary tree, so that every level except the deepest must contain as many nodes as possible; and at the deepest level, all the nodes are as far left as possible.HeapsHeapsA heap is a certain kind of complete binary tree.194222127234535The "heap property"requires that eachnode's key is >= thekeys of its childrenThe "heap property"requires that eachnode's key is >= thekeys of its childrenHeapsHeapsThis tree is not a heap. It breaks rule number 1.1927234535HeapsHeapsThis tree is not a heap. It breaks rule number 2. 21234535HeapsHeapsThis tree is not a heap. It breaks rule number 3. 2135234527Heap implementation of priority queue•Each node of the heap contains one entry along with the entry’s priority, and the tree is maintained so that it follows the heap storage rules using the entry’s priorities to compare nodes. Therefore:•The entry contained by a node has a priority that is greater than or equal to the priority of the entries of the nodes children.•The tree is a complete binary tree.Adding a Node to a HeapAdding a Node to a Heap Put the new node in the next available spot.19422212723453542Adding a Node to a HeapAdding a Node to a Heap-Push the new node upward, swapping with its parent until the new node reaches an acceptable location.19422214223453527Adding a Node to a HeapAdding a Node to a Heap-Push the new node upward, swapping with its parent until the new node reaches an acceptable location.19422213523454227Adding a Node to a HeapAdding a Node to a HeapThe parent has a key that is >= new node, orThe node reaches the root.The process of pushing the new node upward is called reheapification upward.19422213523454227Removing the Top of a HeapRemoving the Top of a Heap-Move the last node onto the root.19422213523454227Removing the Top of a HeapRemoving the Top of a Heap-Move the last node onto the root.194222135232742Removing the Top of a HeapRemoving the Top of a Heap-Push the out-of-place node downward, swapping with its larger child until the new node reaches an acceptable location.194222135232742Removing the Top of a HeapRemoving the Top of a Heap-Push the out-of-place node downward, swapping with its larger child until the new node reaches an acceptable location.194222135234227Removing the Top of a HeapRemoving the Top of a Heap-Push the out-of-place node downward, swapping with its larger child until the new node reaches an acceptable location.194222127234235Removing the Top of a HeapRemoving the Top of a HeapThe children all have keys <= the out-of-place node, orThe node reaches the leaf.The process of pushing the new node downward is called reheapification downward.194222127234235Adding an Entry to a Heap51927 21 422233545As an example, suppose that we already have nine entries that are arranged in a heap with the above priorities.Suppose that we are adding a new entry with a priority 42.The first stepis to add this entry in a way that keeps the binary tree complete. In thiscase the new entry will be the left