Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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;
}
#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());
}
}
}
}
#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);
}>;
#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)