Summary Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) All average times on this table are the same as their worst times except for Insert. *: everywhere in … Read more
Donald Knuth says (The Art of Computer Programming, Third Ed., Vol. 1, p. 435): Several authors began about 1975 to call the pool of available memory a “heap.” He doesn’t say which authors and doesn’t give references to any specific papers, but does say that the use of the term “heap” in relation to priority … Read more
You might like IntervalHeap from the C5 Generic Collection Library. To quote the user guide Class IntervalHeap<T> implements interface IPriorityQueue<T> using an interval heap stored as an array of pairs. The FindMin and FindMax operations, and the indexer’s get-accessor, take time O(1). The DeleteMin, DeleteMax, Add and Update operations, and the indexer’s set-accessor, take time … Read more
There are a number of different solutions for finding running median from streamed data, I will briefly talk about them at the very end of the answer. The question is about the details of the a specific solution (max heap/min heap solution), and how heap based solution works is explained below: For the first two … Read more
The easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.
I think there are several questions buried in this topic: How do you implement buildHeap so it runs in O(n) time? How do you show that buildHeap runs in O(n) time when implemented correctly? Why doesn’t that same logic work to make heap sort run in O(n) time rather than O(n log n)? How do … Read more