Please enable JavaScript.
Coggle requires JavaScript to display documents.
Binary Heap Data Structure and Priority Queue ADT (PriorityQueue (PQ) ADT…
Binary Heap Data Structure
and Priority Queue ADT
PriorityQueue (PQ) ADT
Motivation:
When there are some elements
that need to be treated before others
due to them having a higher urgency/ priority,
we need a data structure that is able to enqueue
and dequeue when needed.
The basic Queue is unable to do so, and hence
we move towards PriorityQueue when handling such
problems.
Important Basic Operations
Enqueue (x)
: Put a new item
x in the PQ (in some order)
Dequeue()
: Return an item y that has the highest Priority (key) in the PQ. If there are >1 items with highest priority, remove the one that is inserted first. (FIFO)
Note that we can denote highest priority to be the smallest key or largest key (depending on how we implement Comparator)
Implementation of a PQ
Using a Circular Array-Based Implementation # 1
Property: The content in the array is always in correct order. (At any point in time) Index 0 (front) refers to element with highest priority
How to achieve property: The array is circular. Hence, we can just manipulate the front and back pointers to define the active part of the array.
Enqueue(x)
: Find the correct insertion point. O(N). You do something like insertion sort where you compare from the back till you reach element with higher priority than x. Keep shifting all the elements you have traversed by 1 index to the right.
Dequeue()
: Return the front most item which has the highest priority: O(1) and then increment your front pointer by 1.
Using a Circular Array-Based Implementation # 2
Property to maintain: Dequeue() always returns the correct item. Don't need to main the relative ordering of the items in the array.
Enqueue(x)
: Put item at the back of the queue: O(1). Also need to increment back pointer.
Dequeue()
: Scan the whole queue and return the first item with highest priority, O(N). Once the item is removed, we may also need to close the gaps, which is also O(N), so Dequeue() has a steep O(N) complexity
To do better for Enqueue(x) and Dequeue(), we are going to implement PQ using Heaps.
Implementing a PQ using Heap
Enqueue (x) : Insert(v)
O(log N)
Dequeue() : ExtractMax()
O(log N)
What is a Binary Heap?
A Binary Heap is a
Complete Binary Tree
.
A Complete Binary Tree is a Binary Tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
If every level including the last is filled, that is a
Perfect Binary Tree.
(At each level, items are filled from left to right)
Height of a Complete Binary Tree is O(log N), where N = number of items
We can store a Complete Binary Tree in a 1-based compact array. We make use of the Breadth-First Traversal (left to right) ranks and put each item in an array where its index = its rank in the Complete Binary Tree. (heapsize <= array size, since array should take into account of a possibility where Complete Binary Tree becomes Perfect Binary Tree)
Navigation Operations:
The below operations are the reason why we use 1-based Array implementation instead of zero-based. (0 * 2 = 0)
parent(i) = floor(i/2), except for i = 1(root)
left(i) = 2 * i, No Left Child when left(i) > heapsize
right(i) = 2 * i + 1, No Right Child when right(i) > heapsize
Apart from storing a Complete Binary Tree, for our Data Structure to be considered as a Heap, it needs to maintain either of the following properties:
A [ parent(i) ] >= A[i]
(except root) (
Max Heap
)
A [ parent(i) ] <= A[i]
(except root) (
Min Heap
)
Binary Heap Operations
O(log N)
Insert (v) {
heapsize ++;
A[heapsize] = v;
ShiftUp(heapsize)
}
O(log N)
ShiftUp/ BubbleUp/ IncreaseKey (i) {
while i > 1 (if current key is the root, option terminates.) &&
A[parent(i)] < A[i] // violates max heap property
swap(A[i] , A[parent(i)];
i = parent(i);
}
O(log N)
ExtractMax / ExtractMin (depending on what type of Heap it is)
int maxValue = A[1]; //int minValue = A[1] for min heap
A[1] = A[heapsize];
heapsize--;
ShiftDown(1);
return maxValue; //return minValue for ExtractMin
}
O(log N)
ShiftDown(i)
while(i <= heapsize){
maxValue = A[i];
maxIndex = i;
if(left(i) <= heapsize && maxValue < A[left(i)]
maxValue = A[left(i)]; maxIndex = left(i);
if(right(i) <= heapsize && maxValue < A[right(i)]
maxValue = A[right(i)]; maxIndex = right(i);
if(maxIndex != i)
swap(A[i] , A[maxIndex])
i = maxIndex;
else break;
O(N log N)
CreateHeap(arr)
int N = arr.length;
A[0] = some dummy int;
for i = 1 to i = N // N
Insert(arr[i - 1]); // log N
A is your Heap arr
arr is your input arr.
O(N)
CreateHeap(arr)
heapsize = arr.length;
for(i = 1 to heapsize) // O(N)
A[i] = arr[i - 1]
for(i = parent(heapsize) down to 1) //O(N / 2)
ShiftDown(i) // O(log N)
Know how to analyze this Algorithm. Something similar could come in exams and many may mistakenly put N log N instead of O N.
HeapSort:
O log N
In Place
Not Stable
Algorithm:
HeapSort(arr)
BuildHeap(arr) // O (N)
N = size(arr)
for(int i = 1 to N)
A[N - i + 1] = ExtractMax() // log N
return A