Algorithm


Problem Name: Data Structures - QHEAP1

Problem Link: https://www.hackerrank.com/challenges/qheap1/problem?isFullScreen=true

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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Tree : Binary Search Tree : Lowest Common Ancestor solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Maximum Element solution in Hackerrank - Hacerrank solution C, C++, java,js, Python