Question

Remarks: In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Do not write a program. Write pseudo codes or explain in words

Question 3: Give a data structure that implements a Min-Heap and the command M ax(S) that returns the maximum in the heap. Try and make the last operation as fast as possible.

Answer 1

Here's pseudo code for min heap implementation :

• We have an array and we have to make it min - heap
• in Build-min-heap function we call min-heapify function for all nodes except leaf nodes, because leaf nodes are alredy in min-heap format as they don't have any children.
• children of i-th node are at 2*i + 1 and 2*i+2 index.
• In min-heapify function we compare given node to its children.
• we swap given node with the child node if the child node have value less then it.
• Time complexity for building min_heap is O(N).

min_heapify(arr,int i,int n)
{
   
    int lowest = i;
    int l = 2*i+1;
    int r = 2*i+2;
    if(l < n && arr[l] < arr[lowest])
        lowest = l;
    if(r < n && arr[r] < arr[lowest])
        lowest = r;
    if(lowest != i)
    {
        swap(arr[lowest],arr[i]);
        min_heapify(arr,lowest,n);
    } 
}

Build_min_heap(arr, int n)
{
    for(int i = n/2-1;i >= 0; i--)
    {
        min_heapify(arr,i,n);
    }
}

Now, come to getting max-element from min-heap.

• In min-heap parent node is lesser than child codes.
• So, we can conclude that non-leaf node cannot be  the maximum element as its child node has a higher value.
• So, now we need to check for leaf-nodes only that which node has highest value.
• There is ceil(n/2) leaf nodes in min heap.
• So time complexity will be O(N).

Pseudo-code :

int findMaximumElement(int heap[], int n) 
{ 
    int maximumElement = heap[n / 2]; 
  
    for (int i = 1 + n / 2; i < n; ++i) 
        maximumElement = max(maximumElement, heap[i]); 
  
    return maximumElement; 
} 

Like, if this helped :)