During the upheap or downheap process, we will need to decide whether or not we should swap the parent node with the child node to restore the heap property. In a min-heap, the heap property is for any node m, m.parent.value ≤ m.value. In a max-heap, the heap property is for any node m, m.parent.value ≥ m.value. When we insert() or delete() a node from the binary heap, we will need to either upheap (if we insert) or downheap (if we delete) to restore the heap's property. This compare_funct is a comparison function that is passed in when we create the binary heap.Īrray: list # O(n) space where n is the number of elements The compare_funct attribute is an indication of whether the binary heap is a max-heap or a min-heap. The second attribute is called compare_funct. In this array, for any element e at index i (where i is in the interval and i is an integer): The first attribute is an array which is used to represent the binary heap. The BinaryHeap class will include 2 attributes. Note that our binary heap allows duplicates. The attribute value is used to store the value that is inserted into the heap, and the attribute index is used to store the index of the node in the array that is used to represent the binary heap.īinaryHeap attributes and comparison function for min-heap and max-heap This class will have 2 attributes: value and index. We will first create a class called Node. (detailed implementation and example below) Implementation (Code) (detailed implementation and example below)Īfter we swap the root with the last element in the array and remove and return the last element in the array, we then continuously compare the current element at the root with its left and right child and swap with either its left or right child until the heap property is restored. Finally, we perform a down heap to restore the heap property. We then remove and return the last element in the array. We swap the root (the first element in the array) with the element at the end of the array. (detailed implementation and example below) We continuously compare the newly added element with its parent and perform the swap operation between that element and its parent until the heap property is restored. We insert() the new element to the end of the array then perform upheap to restore the heap property.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |