HackerRank QHEAP1 problem solution

In this tutorial, we are going to solve or make a solution to the QHEAP1 problem. so here we have Q queries and 3 types of queries. we need to perform these queries on the heap.

Problem solution in Python programming.

from __future__ import print_function
import heapq
try: input = raw_input
except: pass

d = {}
h = []
Q = int(input())
for q in range(Q):
  l = [int(x) for x in input().strip().split(' ')]
  (a,b) = (l[0], l[1] if len(l) > 1 else None)
  if a == 1: heapq.heappush(h,b)
  elif a == 2: # mark for deletion
    if b in d: d[b] += 1
    else: d[b] = 1
  else:
    while True:
      x = h[0]
      if x in d:
        heapq.heappop(h)
        d[x] -= 1
        if d[x] <= 0: del(d[x])
      else: break
    print(x)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    	public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int N = Integer.parseInt(scan.nextLine());
        int[][] arr = new int[N][2];
        
        for(int i = 0; i< N; i++){
            String line = scan.nextLine();
            String[] query = line.split(" ");
            
            arr[i][0] = Integer.parseInt(query[0]);
            if(query.length ==2){
                arr[i][1] = Integer.parseInt(query[1]);
            }
        }
        
        heapMethods(arr);     
    }
    
    public static void heapMethods(int[][] arr){
        int N = arr.length;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        
        for(int i = 0; i<N; i++){
            if(arr[i][0] == 1){
                minHeap.add((arr[i][1]));
            } else if(arr[i][0] == 2){
                minHeap.remove((arr[i][1]));
            } else{
                System.out.println(minHeap.peek());
            }
        }
    }
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    
    int n;
    cin >> n;
    vector<int> vlist;
    
    for(int i = 0; i < n; i ++)
    {
        int c, v;
        c = v = -1;
        cin >> c;
        if(c == 1 || c == 2)
            cin >> v;
        vlist.push_back(c);            
        vlist.push_back(v);            
    }    
    
    multiset<int> uset;
    for(int i = 0; i < n; i ++)
    {
        int c = vlist[i * 2];
        int v = vlist[i * 2 + 1];
        
        if(c == 1)
            uset.insert(v);
        else if(c == 2)
            uset.erase(uset.find(v));
        else
            cout << (*uset.begin()) << endl;
            
            
    }    
    return 0;
}

Problem solution in C programming.

#include <stdio.h>

#define MAX_N 100000

int heap[MAX_N], heap_len;

int Q;
int order, num;

void insert(int number)
{
    int parent, pos;
    int temp;
    heap[heap_len++] = number;
    pos = heap_len - 1;
    parent = pos / 2;
    while(1)
    {
        if(heap[parent] > heap[pos])
        {
            temp = heap[pos];
            heap[pos] = heap[parent];
            heap[parent] = temp;
            pos = parent;
            parent = pos / 2;
        }
        else break;
    }
}

void heap_adjust(int index)
{
    int left, right, min, temp;
    while(1){
        
    left = 2 * index + 1;
    right = 2 * (index + 1);
    min = index;
    if(left < heap_len && heap[index] > heap[left])
        min = left;
    if(right < heap_len && heap[min] > heap[right])
        min = right;
    
    if(min != index)
    {
        temp = heap[min];
        heap[min] = heap[index];
        heap[index] = temp;
        index = min;
    }
    else break;
    
    }
    
}

void delete(int number)
{
    int index;
    int i, temp, pos;
    for(i = 0; i < heap_len; i++)
    {
        if(heap[i] == number)
        {
            index = i;
            pos = heap_len - 1;
            heap_len--;
            if(index < pos)
            {
                heap[index] = heap[pos];
                
                heap_adjust(index);
            }
            
            break;
        }
    }
   
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int i;
    scanf("%d", &Q);
    heap_len = 0;
    for(i = 0; i < Q; i++)
    {
        scanf("%d", &order);
        if(order == 1)
        {
            scanf("%d", &num);
            insert(num);
        }
        else if(order == 2)
        {
            scanf("%d", &num);
            delete(num);
        }    
        else if(order == 3)
        {
            printf("%dn", heap[0]);
        }
    }
    
    
    return 0;
}

Problem solution in JavaScript programming.

function find_parent_idx(node_idx) {
    if(node_idx === 0) {
        return null;
    }
    
    return Math.floor((node_idx - 1) / 2);
}

function find_smaller_child_idx(heap, node_idx) {
    var left_child = node_idx * 2 + 1;
    var right_child = left_child + 1;
    
    if(left_child >= heap.length) {
        return null;
    }
    
    if(right_child >= heap.length) {
        return left_child;
    }
    
    return heap[left_child] < heap[right_child] ? left_child : right_child;
}

function add_to_heap(heap, num) {
    heap.push(num);
    var node_idx = heap.length - 1;
    
    var parent_idx = find_parent_idx(node_idx);
    while(parent_idx !== null && heap[parent_idx] > num) {
        heap[node_idx] = heap[parent_idx];
        heap[parent_idx] = num;        
        node_idx = parent_idx;
        parent_idx = find_parent_idx(node_idx);
    }
}

function delete_from_heap(heap, num) {
    var i, len;
    var node_idx;
    for(i = 0, len = heap.length; i < len; i++) {
        if(heap[i] == num) {
            node_idx = i;
        }
    }
    num = heap.pop();
    if(node_idx == heap.length) {
        return;
    }
    heap[node_idx] = num;
    
    var parent_idx = find_parent_idx(node_idx);
    while(parent_idx !== null && heap[parent_idx] > num) {
        heap[node_idx] = heap[parent_idx];
        heap[parent_idx] = num;        
        node_idx = parent_idx;
        parent_idx = find_parent_idx(node_idx);        
    }
            
    var child_idx = find_smaller_child_idx(heap, node_idx);
    while(child_idx !== null && heap[child_idx] < num) {
        heap[node_idx] = heap[child_idx];
        heap[child_idx] = num;        
        node_idx = child_idx;
        child_idx = find_smaller_child_idx(heap, node_idx);
    }
}

function processData(input) {
    var lines = input.split("n");
    var i, len;
    var cmd;
    var heap = [];
    for(i = 0, len = lines.length; i < len; i++) {
        cmd = lines[i].split(" ");
        if(cmd[0] == 1) {
            add_to_heap(heap, parseInt(cmd[1]));
        } else if(cmd[0] == 2) {
            delete_from_heap(heap, parseInt(cmd[1]));
        } else if(cmd[0] == 3) {
            console.log(heap[0]);
        }
        // console.log(heap);
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});