## Algorithm

Problem Name: Data Structures - QHEAP1

In this HackerRank in Data Structures - QHEAP1 solutions

This question is designed to help you get a better understanding of basic heap operations.

There are 3 types of query:

• "1 v" - Add an element v to the heap.
• "2 v" - Delete the element v from the heap.
• "3" - 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.

Input Format

The first line contains the number of queries, Q.

Each of the next Q lines contains one of the 3 types of query.

Constraints

1 <= Q <= 10**5

10**99 <= v <= 10**9

Output Format

For each query of type 3 , print the minimum value on a single line.

Sample Input

```STDIN       Function
-----       --------
5           Q = 5
1 4         insert 4
1 9         insert 9
3           print minimum
2 4         delete 4
3           print minimum
```

Sample Output

``````4
9
``````

Explanation

After the first 2 queries, the heap contains {4,9} . Printing the minimum gives 4 as the output. Then, the 4**th query deletes 4 from the heap, and the 5**th query gives 9 as the output.

## Code Examples

### #1 Code Example with C Programming

```Code - 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("%d\n", heap[0]>;
}
}

return 0;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - 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;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - 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();

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());
}
}
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - 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);
}>;
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - 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)
``````
Copy The Code &
Advertisements