QHEAP1 HackerRank Solution

QHEAP1 HackerRank Solution

In this QHEAP1 HackerRank solution, This question is designed to help you get a better understanding of basic heap operations.

There are  types of query:

  •  ” – Add an element  to the heap.
  •  ” – Delete the element  from the heap.
  • ” – Print the minimum of all the elements in the heap.

NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.

QHEAP1 HackerRank solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in Python

import heapq as hp


n = int(input())
H = []


for _ in range(n):
    inp = input()
    ind = int(inp[0])
    if ind == 1:
        v = int(inp[2:])
        hp.heappush(H,v)
    elif ind == 2:
        v = int(inp[2:])
        v_ind = H.index(v)
        H[v_ind] = H[-1]
        H.pop()
        if v_ind < len(H):
            hp._siftup(H, v_ind)
            hp._siftdown(H, 0, v_ind)
    else:
        print(H[0])

Problem Solution in Java

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);


        int Q , first, second ;
        int min = Integer.MAX_VALUE;
        List<Integer> arr = new ArrayList<>();


        Q = scan.nextInt();
        while (Q > 0) {
            first = scan.nextInt();
            switch (first) {
                case 1:
                    second = scan.nextInt();
                    arr.add(second);
                    if (second<min || arr.size()==1) min = second;
                    break;
                case 2:
                    second = scan.nextInt();
                    arr.remove(Integer.valueOf(second));
                    if (min == second && !arr.isEmpty()) min = Collections.min(arr);
                    break;
                case 3:
                    System.out.println(min);
                    break;
            }
            Q--;
        }
    }

Problem Solution in JavaScript

class MinHeap {
    constructor() { this.h = [] }
    _parent = (i) => i ? Math.floor((i-1)/2) : null
   
    peek = () => this.h[0]
   
    add(x) {
        let h = this.h
        h.push(x)
        let i = h.length - 1
        let p = this._parent(i)
        while (p !== null && x < h[p]) {
            h[i] = h[p]
            h[p] = x
            i = p
            p = this._parent(i)
        }
    }
   
    remove(x) {
        let h = this.h
        let i
        for (let j = 0; j < h.length; j++)
            if (h[j] == x) i = j
        x = h.pop()
        if(i == h.length) return
        h[i] = x
       
        let p = this._parent(i)
        while (p !== null && h[p] > x) {
            h[i] = h[p]
            h[p] = x
            i = p
            p = this._parent(i)
        }
        let c = this.minChild(i)
        while (c !== null && h[c] < x) {
            h[i] = h[c]
            h[c] = x
            i = c
            c = this.minChild(i)
        }
    }
 
    minChild(i) {
        let h = this.h
        let l = i * 2 + 1
        let r = l + 1
        if (l >= h.length) return null
        if (r >= h.length) return l
        return h[l] < h[r] ? l : r
    }
}


function processData(input) {
    let h = new MinHeap()
    let lines = input.split('\n')
    lines.shift()
    for(let l of lines) {
        let [q, p] = l.split(' ')
        if (q == 1) h.add(+p)
        else if (q == 2) h.remove(+p)
        else if (q == 3) console.log(h.peek())
    }
}
Solve original Problem on HackerRank here. Checkout more HackerRank Problems