1)
Heap
The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. An array A that represents a heap is an object with two attributes:
\(A.length\), which (as usual) gives the number of elements in the array, and \(A.heap-size\), which represents how many elements in the heap are stored within array A.
Root : \(A\left[1\right]\)
Left(i) : \(2i\)
Right (i): \(2i+1\)
Parent (i): \(\lfloor\frac{i}{2}\rfloor\)
Priority Queue
Priority queues are implemented in such a way that they are dequeued according to the priority of the elements.
Operations supported on a priority queue are:
1. addItem(item, priority)
2. getItemWithHighestPriority()
3. changePriority(item, new_priority)
To change priority of an element in our priority queue we need to look it up in less than O(n) time and we can do so by maintaining another data structure such as AVL Tree which allows Search operation in \(O\left(\log n\right)\) time such that each node of the AVL Tree has {item, index}.
Index will point to the index of the item in the array which is our priority queue. In this way when we have to look for an item to change its priority we can look it up in the AVL Tree to know its index in the array.
Also, in our priority queue each node will additionally have a pointer to its corresponding element in the AVL Tree so that once we change the priority of a particular element we can have maximum of logn elements changed in the priority queue and we can update their respective indices in the AVL Tree in O(1) time since we'll be having their direct address and we can make the change.
\(addItem\left(item,\ priority\right)\){
1. Extend Array by one element
2. pos\(\leftarrow\)Put the element at the element with the missing leaf.(end of the array)
3. if( priority < lastElement.priority){ // last element in array before adding the new element
save memory address in pointer of A[pos]\(\leftarrow\)AVL.insert(item, pos) //AVL.insert returns the address of the node inserted
} else {
4. while(pos > 1 and A[Parent(pos)].priority < A[pos].priority){ // O(log n)
exchange A[pos] with A[Parent(pos)]
Update AVL Tree for A[pos] and A[Parent(pos)] //search for A[pos] and update its index.
//search for A[Parent(pos)] & update its index.
5. pos = Parent(pos)
}
save memory address in pointer of A[pos]\(\leftarrow\)AVL.insert(item, pos) //AVL.insert returns the address of the node inserted
}
Time Complexity Analysis: Time complexity will be O(log n)
Space Complexity Analysis: O(1) as we are creating the AVL tree before-hand.