pburakov "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.
roufamatic I had the same response. Once you need to search the heap for a specific value, you're really stuck with linear time. So this may not be the best data structure to use if the operation is expected to be called very often.
That said, I think there are real-world use cases for this. Very simply, suppose you have a priority queue filled with a bunch of random work items. Every once in a while, somebody submits work, then smacks their head and says "oh, I forgot to do XXXXX." That person would like to remove the item from the queue, then resubmit. Depending on how big the queue is and how often this happens, you might be OK with the linear search.
gschoen Darn! I thought I was being clever.
I wrote a routine that recursively searched the left child or the right child (if not in the left child) for the value. I initially thought that this should have a logarithmic run time but on second thoughts, in a worst case scenario, it may be even worse than linear time.
victortang_com I hope ou realized the problem with implementing heap with Tree structure. It is recommended to implement heap using array.
gschoen Sure. By "left child" I mean calculate the index position of the left child and by "right child" I mean calculate the index position of the right child.
int findIndex(int *A, int n, int value, int size) { int tmpIndex; if (A[n] == value) { return n; } else if (2*n > size) { return -1; } else if ((tmpIndex = (findIndex(A, 2*n, value, size))) > 0) { return tmpIndex; } else if ((2*n + 1) > size) { return -1; } else { return findIndex(A, 2*n + 1, value, size); } }
kkworden Actually, you can achieve logarithmic O(log n) time for removal of arbitrary elements.
What I did was store the indicies of certain values in a dictionary, then when I wanted to remove a value, I'd have the index of that item in the array.
To remove some element, simply overwrite the value of the item in the array you want to remove with the value of last item in the heap (going top to bottom, left to right), and then remove the last item in the heap. The index can found by the dictionary lookup. Then all you have to do is "re-heapify" from that index. Dictionary lookups are constant, so the removal operation is on the same order as re-heapifying (i.e. swapping all items in the heap until the heap property is satisfied); an O(log n) operation.
I had implemented a linear removal operation, but it timed out so I resorted to this. I'd be happy to explain further if you all are interested.
humoyun_ahmad how do you maintain dict? I mean when do you enter values into dict?
kkworden Any time you insert an element, create a new key for that element, with the value being the index in the array where that element is stored. Every time you swap elements, you update the indices in the dictionary. When you remove an element from the heap, simply delete that key from the dictionary.
gastonfontenla But if you did it that way, then, why to even bother to write a heap ??
kkworden Because the challenge is to write a heap...?
gastonfontenla I mean, you are using another data structure (not a heap) for that index-searching task. It's like, you could better use that data structure instead, and forget the heap. I haven't solved it with maps or sets because I want to think in a pure-heap solution, maybe two heaps or something like that? I don't know, just saying...
kkworden You are right, but also notice that this question asks you to remove an arbitrary element from the heap.
Pure heaps do not support the removal of arbitrary elements, as other users have pointed out.
So, in order to pass this challenge, I used a dictionary.
If the question asked us to write a pure heap (that does not support the removal of arbitrary elements), then there would be no need for the dictionary in the first place.
ross_mcconnell53 Dijkstra's algorithm for shortest path and Prim's algorithm for finding a minimum spanning tree are usually considered applications of heaps, even though they could be implemented with binary trees. Heaps are more efficient. They require kkworden's technique of providing a table or dictionary for looking up the current location of an element with the given identifier. The heap operations 'reduce-key' and 'delete' require the table. See Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms," third edition. So there are a lot of reasons to do it the way the problem setter has suggested.
gastonfontenla You don't get what I meant. I said that he just adds a Priority Queue for no reason. I tried to say that there must be a solution with pure PQ implementation.
mikael_magnuson I agree that this is possible, but to the OP's point, this is not a basic heap operation.
someknowit But, you don't need to really physically remove the element from the heap until it became the smallest. This can lead to O(1) runtime for the delete operation.
And, no need to search.
gsandeep_2482 Interesting!
orthonormalize Clever!
e_sovetkin Thanks, that is a very good idea. In fact we can keep a second heap, where we keep a record of deleted values.
mugurbil what if you then add it?
Merter_Sualp 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:
- An identifier to show the last element of the heap, since all capacity of the array may not be filled.
- A mechanism to put the minimum element to the top of the heap.
- A search algorithm to find the desired element to delete. This step is crucial.
- Another mechanism to preserve the heap property after deleting the given element.
The skeleton code below addresses these 4 requirements.
int lastacts 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 asheap[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 ofi. The left one will have the index of2*iand the right one will have one more of if, which equals to2*i+1When 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); }
lutfan Great solution. Can I ask why there's a need for the sink method? Why can't we just use the swim method to preserve heap property after deletion?
Merter_Sualp Actually, the answer to this question fills a cavity in my explanation. When I say that a heap can be thought to be a binary tree, I implicitly think of it is a complete binary tree. Therefore, we should also preserve the completeness.
Keeping that in mind, it is clear that we need to swap the deleted element inside the tree with the last leaf child, which is purposely the last element of our array. By this, we are sure that the completeness is preserved. It is
heap[last]in my code. Let's call itlastChild.So what about
lastChildnow residing inside the tree after deletion? We know that it must be greater than its children now, if there are any. That was why that element was the last member of the heap. So this very situation breaks the heap property. To restore, it must go downwards through the complete binary tree. That is wheresink()becomes handy.Can't we use a non-complete binary tree? Most probably, but then we must keep track of deleted indicies in the array. Moreover, the array will consume much more space than it actually needs. I have not coded but we can also shrink the size of the array if the
lastbecomes a predefined portion (maybe 1/4) of array capacity. No matter what, I will try to code that implementation and share if it succeeds.
nC3rtainity Wow! Thanks a lot.. just a swim() function and boom no more time outs! :D
nC3rtainity but wait I don't get a few things-
1.my swim() function just swaps finds the min_pos and then swaps heap[min_pos] and heap[1]. wouldn't your swim() cost you extra swaps.
2.why did you search left tree first and then the right tree? why not just iterate through heap[1] to heap[last]?
Merter_Sualp I think I am missing something. When I add a new element, I put it at the very end of the array. Then, I find its eventual position by
swim()ing up the tree. Could you post your code so I can follow your logic much more clearly please?It is a matter of taste in fact. Since the heap is not a binary search tree, there is no guarantee that the element we are looking for will be either in the right or in the left subtree. We can also scan through the whole array as you have mentioned. In any way, the worst case time complexity won't change. My search has a slim chance of having a better average case time complexity but I cannot prove theoretically. Both are ok in this problem.
nC3rtainity Your swim function is absolutely fine, but what I dont get is why you swap(heap, parent, pos) everytime in the while loop.
swim()
void swim() { // finding the min element. int min_pos = 1; for(int i=2; i<=N; ++i) { if(Heap[i]< Heap[min_pos]) { min_pos = i; } } // swapping the min element in the heap with the element at 1st position. int temp = Heap[1]; Heap[1] = Heap[min_pos]; Heap[min_pos] = temp; }
my main()
int main() { int Q; // no of queries cin >> Q; while(Q--) { int query; cin >> query; if(query == 1) { int num; cin >> num; Heap[ ++N ] = num; swim(); } else if( query == 2) { int num; cin >> num; remove_heap(num); build_minheap(); } else if( query == 3) { cout << Heap[1] << endl; } }
let me know if you see some scope for improvement; :)
Merter_Sualp Now I think I get it. The reason we swap is to preserve the heap property all over the tree. When a new element is added, it may be the current smallest one. You do it by looking at every element of the heap and it is O(N) time. My solution does it in O(logN). I only walk on a branch from leaf up until to the root.
nC3rtainity But when you are swapping variables it won't preserve heap property.
I guess I can only use an array for showing it here.
Ex - 1 4 3 7 8 9 10 <- min heap, last = 8 if we insert 1 in the heap. 1 4 3 7 8 9 10 1 <- heap[last] = 1 , parent = 4 1 4 3 **7** 8 9 10 **1**<- swaps 1 4 3 1 8 9 10 7 <- pos = 4, parent = 2 1 **4** 3 **1** 8 9 10 7<- swaps 1 1 3 4 8 9 10 7 <- the heap property not maintained
But yea your code does move around smaller values and towards the root of the heap, which is why I thought it could be more efficient.
As far as I know one cannot maintain heap property after inserting an element and manipulating a part of the tree. You would have to do heapify of all nodes starting from last/2.
Merter_Sualp I think in the last state of the array, heap property is preserved acording to this info.
- Root 1 is parent of 1 & 3
- Left child 1 is parent of 4 & 8
- 3 is parent of 9 & 10
- 4 is parent of 7.
If you think it is not, what should be the answer then?
nC3rtainity oh yea sorry my mistake! yea it's fine. thanks :)
liuzhenchangxc Your method for deletion is not completely correct althought it can pass all the test cases. After you swap the last element with the element to be deleted, you should check if the new element is larger than the parent, if not, a swim operation is needed instead of the sink.
liuzhenchangxc In fact i think you can just invoke swim() method before or after you invoke sink() method.
Merter_Sualp Let me try to understand your case with an example. The heap elements can be: - 1 12 5 13 20 6 7
Assuming we are required to delete 13, what my code does is swap the last element, 7 with the fourth element, 13. Now the heap is: - 1 12 5 7 20 6
Here, 7 is the child of 12. The heap property is violated. So, either 7 must
swim()or 12 mustsink()But my code does not cover this case. So you are absolutely correct. Thank you. I will update my code accordingly.
airibo Still, findInHeap takes O(n) time in worth case (where the tree is complete and element to be found is in right most leaf).
nd26041998 In Wikipedia they say that "n computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of node P is greater than the key of node C. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node." Hmm I think it seems make a contradiction to your opinion.
pareek_kunal83 I implemented a basic Heap in Python3 with linear deletion time. It passed all cases except 4. I also thought the deletion was probably the weak spot, the above algo for deletion was what I was thinking about as well.
ccordero I really wouldn't have classified this as an Easy algorithm... I tried to implement this as a class with Node objects and I kept timing out on Case 8 and Case 9. When I used an array implementation of a heap, it was able to pass, but after much work and stress trying to get an algorithm fast enough to arbitrarily remove a node.
Tsukuyomi1 [deleted]
Biprodas 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; } } }
Snigdha_Sanat Thanks a lot. One question- is swap an inbuilt function in c++?
tjs_4297 [deleted]carlostse [deleted]
lateotw Finally figured out why 8 and 9 were timing out, the trick (for Python) here is to only worry about re-heapify if the value been deleted is the root.
rcmedeiros And also, if the value being added is less than the root. Rebalance only when the root is compromised.
deadendtux Thank you for this thought, I spent lot of time with this time out.
SherMM Can't you just call heappop() for that? I don't really see how you can avoid calling heapify in some cases. Removing an element can change the structure of the heap. Which might affect later deletions. If using Python, isn't everyone just using heapq? If you use heappush you don't have to worry about heapify. Only have to heapify if deletion is a non-root node.
pahire heappop only deletes the smallest element, so it cannot be used for the delete operation of this problem
jack_kinsella I want to add that I didn't encounter timeout issues with Python(3) when re-heapifying upon every delete. This suggets that there's some optimization you might be able to apply to your code to speed her up.
jack_kinsella One idea would be to use pop() to delete a switched element, since this is faster than deleting an element in the middle of a list.
gurkohli In C++, I solved it by heapifying only the list after the position at which the element was removed instead of heapifying it from beginning. Was enough time saved to pass all the tests.
harikrishnakera Thanks ,it helped me to pass all the test cases.
pdog1111 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:])
enss [deleted]pdog1111 what makes you think its faster? my understanding is that the performance should be very similar. see for example: https://wiki.python.org/moin/TimeComplexity. also your item_lookup will grow without bound as you add and delete items since nothing is ever actually deleted.
Rys23 My Java solution
public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(); for(int i = 0; i < n; i++) { int q = sc.nextInt(); switch(q) { case 1 : pQueue.add(sc.nextInt()); break; case 2 : pQueue.remove(sc.nextInt()); break; case 3 : System.out.println(pQueue.peek()); break; } } } }
sunng By the way. isn't Binary Search Tree a better solution for this?
Removing item from heap might take O(n) without optimization.
maximshen I think it is O(logN). Alternatively, you can use PriorityQueue, Implementation note from JavaDoc: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
Mirrage [deleted]
Honoo [deleted]
ankurk007 Python3 using heapq:
from heapq import heappush, heappop valheap = [] delheap = [] q = int(input().strip()) for i in range(q): lst = list(map(int, input().strip().split(' '))) if lst[0] == 1: heappush(valheap, lst[1]) elif lst[0] == 2: if valheap[0] == lst[1]: heappop(valheap) else: heappush(delheap, lst[1]) elif lst[0] == 3: check = bool(delheap) while check: if delheap[0] == valheap[0]: heappop(delheap) heappop(valheap) check = bool(delheap) else: check = False print (valheap[0])
ephilippona 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; }
MPrashanthi This is the cleanest code so far but can you explain printMin()...I think i followed but just for more clarity?
Tell me if i got this right --> If minimum element of pq is removed it becomes minimum of pqRemove, if second minimum element is removed it becomes second minimum in pqRemove. We can directly print if minimum wasnt deleted which is the while loop condition. right?
ephilippona Basically if pqremove isnt empty and we havent found the smallest element in pq yet it means we dont care about these values. We can throw them away from both priority queues's since they were removed by the user.
Sort 158 Discussions, By:
Please Login in order to post a comment