It depends on what the type of the heap is. If it’s a standard heap where every node has up to two children and which gets filled up that the leaves are on a maximum of two different rows, you cannot get better than O(n) for merge. Just put the two arrays together and create … Read more
You would use a min-max-median heap to find the min, max and median in constant time (and take linear time to build the heap). You can use order-statistics trees to find the kth smallest/largest value. Both of these data structures are described in this paper on min-max heaps [PDF]. Min-max heaps are binary heaps that … Read more
The build-heap algorithm starts at the midpoint and moves items down as required. Let’s consider a heap of 127 items (7 levels). In the worst case: 64 nodes (the leaf level) don’t move at all 32 nodes move down one level 16 nodes move down two levels 8 nodes move down three levels 4 nodes … Read more
Searching for an element in a heap of size N is not O(K). First, it does not make sense that the time complexity for finding one element depends on the number of elements you are trying to extract (which is what K represents). Also, there is no such thing as searching in a heap — … Read more
The speaker is wrong in this case. The actual cost is O(n * log(t)). Heapify is called only on the first t elements of the iterable. That’s O(t), but is insignificant if t is much smaller than n. Then all the remaining elements are added to this “little heap” via heappushpop, one at a time. … Read more
Nothing much, to be honest. I would imagine that the word heap was simply taken with it’s everday (non-technical) usage and applied to these two concepts individually as reasonably good analogies. In the first case (tree data structure meaning), the description heap is most appropiate because “greater” objects are placed higher up in the tree … Read more
Well, your intuition was right that we need extra data structure to achieve O(klogk) because if we simply perform operations on the original heap, the term logn will remain in the resulting complexity. Guessing from the targeted complexity O(klogk), I feel like creating and maintaining a heap of size k to help me achieve the … Read more
It is idiomatic to provide couple of overloads of the operator[] function – one for const objects and one for non-const objects. The return type of the const member function can be a const& or just a value depending on the object being returned while the return type of the non-const member function is usually … Read more
There is a much better reference for the claim that average time heap insertion is O(1): the 1991 paper “Average Case Analysis of Heap Building by Repeated Insertion” by Hayward & McDiarmid. (This paper is linked in what is currently reference 4 of the Wikipedia article.) That paper in turn references a 1975 paper by … Read more
The logical argument is as follows std::priority_queue is a container adaptor; basic memory considerations make the back the preferred place for modifications (with pop_back() and push_back()) for sequence containers such as std::vector. the priority_queue primitives are based on std::make_heap (constructor), std::pop_heap + container::pop_back (priority_queue::pop) and on container::push_back + std::push_heap (priority_queue::push) pop_heap will take the front … Read more