In a max-heap, if the newly added node has a value that is larger than the value that its parent holds (i.e. If the heap property is not violated, it will return 0.įor the upheap process, node 1 will be the newly added node, and node 2 will be its parent.

The comparison function will compare the values that are stored in 2 nodes and return 1 if the heap property is violated and the 2 nodes need to be swapped to restore the heap property. This is why we need different comparison functions (or compare_funct) for min-heap and max-heap. 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.

The parent of e is at index floor((i-1)/2).We will use an array to represent the binary heap. In a min-heap, for any node m, m.parent.value ≤ m.value (min-heap property). To create a min-heap-based priority queue, we create an instance of the PriorityQueue class and pass in the comparing mechanism for a min heap as an argument. If we want the priority in the priority queue to be 'smaller value, higher priority', we use a min-heap-based priority queue.

When we want to enqueue() priority queue, we call the insert() method of the BinaryHeap class. Whenever we want to dequeue() the priority queue, we call the delete() method of the BinaryHeap class. The PriorityQueue class will be the Subclass of the BinaryHeap class. The BinaryHeap class will be the Superclass. We will implement a heap-based priority queue by using the binary heap. The priority queue that we build will allow duplicates. A priority queue that follows the rule 'smaller value, higher priority' will remove and return the smallest element upon deletion. For example, a priority queue that follows the rule 'larger value, higher priority' will remove and return the largest element upon deletion. However, while a queue's dequeue() and enqueue() methods follow the rule First in First out (FIFO), a priority queue will remove and return the value upon deletion based on a priority. In this article at OpenGenus, we will implement priority queue in Python, utilizing Object-Oriented Programming (OOP).

Python priority queue use