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){
} 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;
}
}

{
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];

}

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("%d\n", 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;
}

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) {
} 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);
});