We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Heap
  4. QHEAP1
  5. Discussions

QHEAP1

Sort 385 Discussions, By:

  • pburakov
     + 7 comments

    "This question is designed to help you get a better understanding of basic heap operations." Query 2 - Delete the element u from the heap " .. sigh...

    Deleting arbitrary value from a heap / priority queue is not a basic operation the heap is designed for. Heaps rep. invariant only guarantees a constant time access to min/max element. Arbitrary deletion is done via swapping a node (which first has to be found in linear time) with the last element, plus then everything "below" it has to be fixed (worst case log(n) time) to garantee heap properties. Anything better than that can be implemented as a BST or a hashmap(?), but that effectively makes it a BST or a hashmap and not a conventional heap. No offence, just my 2 cents.

  • Merter_Sualp
     + 7 comments

    The heap structure can be thought to be a binary tree. The heap property states that any parent is smaller than both of its children. This guarantees that the root has the smallest element. In the basic heap, there are insert, delete and peek operations, as in this question. However, there is a slight difference in delete operation. In the basic heap delete, only root is removed. However, this very exercise requires the deletion of a specific value in the heap. Therefore, we must devise a way to find that value by using the heap property. This also makes us to keep the average (not worst) time complexity within the boundries of O(logN).

    When an interviewer asked a question like this, most probably we will not be allowed to use data structures provided by the language we are coding with. Rather, we need to implement it from scratch. Let's assume we are using Java and basic arrays. Moreover, we do not know the max operations beforehand.

    What we will need are:

    1. An identifier to show the last element of the heap, since all capacity of the array may not be filled.
    2. A mechanism to put the minimum element to the top of the heap.
    3. A search algorithm to find the desired element to delete. This step is crucial.
    4. Another mechanism to preserve the heap property after deleting the given element.

    The skeleton code below addresses these 4 requirements. int last acts as the boundry identifier, swim() puts the minimum element to the top. findInHeap() searches for the element to be deleted. sink() restores the heap property after deletion. When adding an element, the array can be full. To enlarge it, I add a method, doubleSizeOf() to double the capacity of the heap.

      public static void main(String[] args) {
    int[] heap = new int[16];
    int last = 1;
    Scanner in = new Scanner(System.in);
    int queries = in.nextInt();
    for (int q=0; q<queries; q++) {
      int op = in.nextInt();
      switch (op) {
        case 1:
          int value = in.nextInt();
          if (last == heap.length) {
            heap = doubleSizeOf(heap);
          }
          heap[last] = value;
          swim(heap, last);
          last++;
          break;
        case 2:
          value = in.nextInt();  
          int posToDelete = findInHeap(heap, value, last);
          last--;
          swap(heap, posToDelete, last);
          sink(heap, posToDelete, last);
          swim(heap, posToDelete);
          break;
        case 3:
          if (last > 1) {
            System.out.println(heap[1]); 
          }
          break;
        default:
          ;
      }
    }
    in.close();
  }
  
  private static int[] doubleSizeOf(int[] heap) {
    int [] doubleHeap = new int[heap.length*2];
    for (int i=0; i<heap.length; i++) {
      doubleHeap[i] = heap[i];
    }
    return doubleHeap;
  }

    In my implementation, I followed what I remember from Algorithms 4th Edition by Sedgewick. I keep an integer array heap[]and the root of the heap is positioned as heap[1]. Hence the index 0 is never used. This gives us the ability to simply calculate the positions of the left and right children of any parent. Let the parent have an index of i. The left one will have the index of 2*i and the right one will have one more of if, which equals to 2*i+1 When we want to add a new element, we put it as the last element of the array and swim that element upwards the binary tree. 

      private static void swim(int[] heap, int pos) {
    int parent = pos/2;
    while (parent>0 && heap[pos]<heap[parent]) {
      swap(heap, parent, pos);
      pos = parent;
      parent = pos/2;
    }
  }
  
  private static void swap(int[] heap, int from, int to) {
    int temp = heap[from];
    heap[from] = heap[to];
    heap[to] = temp;
  }

    While going up, we move until the parent is smaller than its new child. If not, we swap the parent and the new child. This can break the heap property so each swap requires one more iteration.

    The most critical part is finding the element to be deleted. Since parents are always smaller than the children, we can traverse the tree to find the desired child. However, we cannot use binary search, since there is no strict ordering between the children. Hence, we will first try the left subtree, if it is not there, we must check the right one.

      private static int findInHeap(int[] heap, int key, int last) {
    return findInHeapStartingFrom(heap, key, last, 1);
  }
  
  private static int findInHeapStartingFrom(int[] heap, int key, int last, int pos) {
    if (last <= pos) {
      return -1;
    }
    if (heap[pos] == key) {
      return pos;
    }
    int foundInLeft = findInHeapStartingFrom(heap, key, last, pos*2);
    if (foundInLeft > -1) {
      return foundInLeft;
    }
    return findInHeapStartingFrom(heap, key, last, pos*2+1);
  }

    After getting the position of the element, we swap that with the last member of the heap and decrease the indicator by one. Therefore, there may be deleted elements which still linger in the array but cannot be accessed by my implementation. The previously last but now became an internal node element may quite possibly break the heap property. We should either sink it downwards or swim it upwards the binary tree, as proposed by liuzhenchangxc.

      private static void sink(int[] heap, int pos, int last) {
    int left = pos*2;
    int right = pos*2+1;
    int posToSwap = pos;
    if (left<last && heap[left]<heap[posToSwap]) {
      posToSwap = left;
    }
    if (right<last && heap[right]<heap[posToSwap]) {
      posToSwap = right;
    }
    if (pos == posToSwap) {
      return;
    }
    swap(heap, pos, posToSwap);
    sink(heap, posToSwap, last);
  }

  • pdog1111
     + 5 comments

    simple solution in python using heapq. the trick is to use an item_lookup set for lazy deletes.

    from sys import stdin
from heapq import heappush, heappop

heap = []
item_lookup = set()

def push(v):
    heappush(heap, v)
    item_lookup.add(v)
    
def discard(v):
    item_lookup.discard(v)
    
def print_min():
    while heap[0] not in item_lookup:
        heappop(heap)
      
    print heap[0]
    
cmds = {
    1: push,
    2: discard,
    3: print_min
}

n = int(stdin.readline())
for _ in range(n):
    data = map(int,stdin.readline().split(" "))
    cmds[data[0]](*data[1:])

  • Biprodas
     + 3 comments

    At last successfully passed all test cases. here is my code below..

    #include<bits/stdc++.h>
using namespace std;

#define NN 100000 //Heap size

struct minHeap{
    int n; //number of nodes in heapArr
    int heapArr[NN+1]; //array is 1 based
    minHeap(){ n=0 ;}
    void min_heapify(int index);
    void insert(int k);
    int search(int k);
    void deleteKey(int k);
    int getMin();
};
void minHeap::min_heapify(int i){
        int l = 2*i;
        int r = 2*i+1;
        int min = i;
        if(l<n && heapArr[l]<heapArr[min])
            min = l;
        if(r<n && heapArr[r]<heapArr[min])
            min = r;
        if(min != i){
            swap(heapArr[i],heapArr[min]);
            min_heapify(min);
        }
    }
void minHeap::insert(int k){
        if(n==NN) return;
        n++;
        heapArr[n]= k;
        int p= n;
        while(p>1){
            int pr= p/2;
            if(heapArr[pr]>heapArr[p]){
                swap(heapArr[pr],heapArr[p]);
                p= pr;
            }
            else break;
        }
}
int minHeap::getMin(){
    if(n==0) return -1;
    else return heapArr[1];
}

int minHeap::search(int ele){
    for(int i=1;i<=n;i++){
        if(heapArr[i] == ele)
            return i;
        }
        return -1;
    }

void minHeap::deleteKey(int ele){
        int index = search(ele);
        heapArr[index] = heapArr[n];
        n--;
        min_heapify(index);
    }
int main(){
    minHeap h;
    int q, t, x;
    cin>>q;
    while(q--){
        cin>>t;
        if(t==1){
            cin>>x;
            h.insert(x);
        }
        else if(t==2){
            cin>>x;
            h.deleteKey(x);
        }
        else{
            cout<<h.getMin()<<endl;
        }
    }
}

  • ephilippona
     + 1 comment

    A c++ solution using 2 heaps. 1 to track the overall min item and 1 to track the min of the removed items.

    #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int> > pq;
priority_queue<int, vector<int>, greater<int> > pqRemove;

void add(){
    int n;
    cin>>n;
    pq.push(n);
}

void remove()
{
    int n;
    cin>>n;
    pqRemove.push(n);
    
}

void printMin(){
    
    while(!pqRemove.empty() && pqRemove.top() == pq.top()){
        pq.pop();
        pqRemove.pop();
    }
    cout<<pq.top()<<endl;
}
    
int main() {

    int q;
    cin>>q;
    while(q!=0){
        int command;
        cin>>command;
        if(command == 1)
            add();
        else if(command == 2)
            remove();
        else if(command == 3)
            printMin();
        
        q--;
    }
    return 0;
}
Load more conversations