You can remove the i-th element from a heap quite easily: h[i] = h[-1] h.pop() heapq.heapify(h) Just replace the element you want to remove with the last element and remove the last element then re-heapify the heap. This is O(n), if you want you can do the same thing in O(log(n)) but you’ll need to … Read more
heapq is a binary heap, with O(log n) push and O(log n) pop. See the heapq source code. The algorithm you show takes O(n log n) to push all the items onto the heap, and then O((n-k) log n) to find the kth largest element. So the complexity would be O(n log n). It also … Read more
You can use the Median of Medians algorithm to find median of an unsorted array in linear time.
A priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation. A heap is a data structure. It is a name for a particular way of storing data that makes certain operations very efficient. It just so happens that a … Read more
The heapq module maintains the heap invariant, which is not the same thing as maintaining the actual list object in sorted order. Quoting from the heapq documentation: Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] … Read more
In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 … Read more
Queue.PriorityQueue is a thread-safe class, while the heapq module makes no thread-safety guarantees. From the Queue module documentation: The Queue module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads. The Queue class in this module implements all the required locking semantics. It depends … Read more
According to the example from the documentation, you can use tuples, and it will sort by the first element of the tuple: >>> h = [] >>> heappush(h, (5, ‘write code’)) >>> heappush(h, (7, ‘release product’)) >>> heappush(h, (1, ‘write spec’)) >>> heappush(h, (3, ‘create tests’)) >>> heappop(h) (1, ‘write spec’) So if you don’t … Read more
For Java 8, updating on an existing answer: You can use Java Priority Queue as a Heap. Min Heap: –> to keep the min element always on top, so you can access it in O(1). PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); Max Heap: –> to keep the max element always on top, the same order as … Read more
Use it whenever you need quick access to the largest (or smallest) item, because that item will always be the first element in the array or at the root of the tree. However, the remainder of the array is kept partially unsorted. Thus, instant access is only possible to the largest (smallest) item. Insertions are … Read more