My question is from the solution in leetcode below, I can&#39;t understand why it is `O(k+(n-k)log(k))`.


Supplement: Maybe the complexity isn&#39;t that, in fact I don&#39;t know the time complexity of `heappush()` and `heappop()`

    # O(k+(n-k)lgk) time, min-heap
    def findKthLargest(self, nums, k):
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
        for _ in xrange(len(nums)-k):
            heapq.heappop(heap)
        return heapq.heappop(heap)

What&#39;s the time complexity of functions in heapq library

[Wikipedia][1] says: 

&gt; Selection algorithms: Finding the min,
&gt; max, both the min and max, **median**, or
&gt; even the k-th largest element can be
&gt; done in linear time using heaps.

All it says is that it can be done, and not how.

Can you give me some start on how this can be done using heaps?

  [1]: http://en.wikipedia.org/wiki/Heap_(data_structure)#Heap_applications

How do I find the median of numbers in linear time using heaps?

What is the official way of peeking in a python heap as created by the heapq libs? Right now I have

    def heappeak(heap):
      smallest = heappop(heap)
      heappush(heap, smallest)
      return smallest

which is arguably, not very nice. Can I always assume that `heap[0]` is the top of the heap and use that? Or would that assume too much of the underlying implementation?

Peeking in a heap in python

I&#39;m learning data structures and every source tells me not to use index 0 of the array while implementing heap, without giving any explanation why. I searched the web, searched StackExchange, and couldn&#39;t find an answer.

Why in a heap implemented by array the index 0 is left unused?

&gt; **Possible Duplicate:**  
&gt; [Rolling median algorithm in C](https://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c)  

&lt;!-- End of automatically inserted text --&gt;

&gt; Given that integers are read from a data stream. Find median of elements read so far in efficient way. 

Solution I have read: We can use a max heap on left side to represent elements that are less than the effective median, and a min heap on right side to represent elements that are greater than the effective median.

After processing an incoming element, the number of elements in heaps differ at most by 1 element. When both heaps contain the same number of elements, we find the average of heap&#39;s root data as effective median. When the heaps are not balanced, we select the effective median from the root of heap containing more elements.

But how would we construct a max heap and min heap i.e. how would we know the effective median here? I think that we would insert 1 element in max-heap and then the next 1 element in min-heap, and so on for all the elements. Correct me If I am wrong here.

Find running median from a stream of integers

I am looking for a .NET implementation of a priority queue or heap data structure

&gt; Priority queues are data structures that provide more flexibility than simple sorting, because they allow new elements to enter a system at arbitrary intervals. It is much more cost-effective to insert a new job into a priority queue than to re-sort everything on each such arrival.
&gt;
&gt; The basic priority queue supports three primary operations:
&gt;
&gt; * Insert(Q,x). Given an item x with key k, insert it into the priority queue Q.
&gt; * Find-Minimum(Q). Return a pointer to the item
whose key value is smaller than any other key in the priority queue
Q.
&gt; * Delete-Minimum(Q). Remove the item from the priority queue Q whose key is minimum


Unless I am looking in the wrong place, there isn&#39;t one in the framework. Is anyone aware of a good one, or should I roll my own?

Priority queue in .Net

Why are the runtime heap used for dynamic memory allocation in C-style languages and [the data structure][1] both called &quot;the heap&quot;? Is there some relation?


  [1]: http://en.wikipedia.org/wiki/Heap_(data_structure)

Why are two different concepts both called &quot;heap&quot;?

What is the difference between a heap and BST? 

When to use a heap and when to use a BST? 

If you want to get the elements in a sorted fashion, is BST better over heap?

Heap vs Binary Search Tree (BST)

Can someone help explain how can building a heap be *O(n)* complexity? 

Inserting an item into a heap is *O(log n)*, and the insert is repeated n/2 times (the remainder are leaves, and can&#39;t violate the heap property). So, this means the complexity should be *O(n log n)*, I would think.

In other words, for each item we &quot;heapify&quot;, it has the potential to have to filter down (i.e., sift down) once for each level for the heap so far (which is *log n* levels).

What am I missing?

How can building a heap be O(n) time complexity?

Besides the obvious answer of a Priority Queue, when would a heap be useful in my programming adventures?

When would I want to use a heap?

I am porting a C++ library to Java and I need a heap data structure. Is there a standard implementation or will I need to do it myself?

Is there a Heap in java?

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,

&gt; The children’s subtrees each have size at most **2n/3**—the worst case
&gt; occurs when the bottom level of the tree is exactly half full.

I understand why it is worst when the bottom level of the tree is exactly half full. And it is also answered in this question https://stackoverflow.com/questions/6859514/worst-case-in-max-heapify

My question is how to get 2n/3? 

Why if the bottom level is half full, then the size of the child tree is up to 2n/3?

How to calculate that?

Thanks


Worst case in Max-Heapify - How do you get 2n/3?

I wish to hold a heap of objects, not just numbers.  They will have an integer attribute in them that the heap can sort by.  The easiest way to use heaps in python is heapq, but how do I tell it to sort by a specific attribute when using heapq?

How to make heapq evaluate the heap off of a specific attribute?

In python there&#39;s a built-in [`heapq`](https://docs.python.org/3/library/heapq.html) algorithm that gives you `push`, `pop`, `nlargest`, `nsmallest`... etc that you can apply to lists. However, there&#39;s also the [`queue.PriorityQueue`](https://docs.python.org/3/library/queue.html#queue.PriorityQueue) class that seems to support more or less the same functionality. What&#39;s the difference, and when would you use one over the other?

What&#39;s the difference between heapq and PriorityQueue in python?

I tried [&quot;heapq&quot;](https://docs.python.org/3/library/heapq.html) and arrived at the conclusion that my expectations differ from what I see on the screen. I need somebody to explain how it works and where it can be useful.

From the book [Python Module of the Week](http://pymotw.com/2/articles/data_structures.html#sorting) under paragraph **2.2 Sorting** it is written

&gt; If you need to maintain a sorted list as you add and remove values,
&gt; check out heapq. By using the functions in heapq to add or remove
&gt; items from a list, you can maintain the sort order of the list with
&gt; low overhead.

Here is what I do and get.
    
    import heapq
    heap = []
    
    for i in range(10):
        heap.append(i)
    
    heap
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    heapq.heapify(heap)    
    heapq.heappush(heap, 10)    
    heap
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    
    heapq.heappop(heap)
    0    
    heap
    [1, 3, 2, 7, 4, 5, 6, 10, 8, 9] &lt;&lt;&lt; Why the list does not remain sorted?
    
    heapq.heappushpop(heap, 11)
    1
    heap
    [2, 3, 5, 7, 4, 11, 6, 10, 8, 9] &lt;&lt;&lt; Why is 11 put between 4 and 6?

So, as you see the &quot;heap&quot; list is not sorted at all, in fact the more you add and remove the items the more cluttered it becomes. Pushed values take unexplainable positions.
What is going on? 

What is Python&#39;s heapq module?

Python includes the heapq module for min-heaps, but I need a max heap.  What should I use for a max-heap implementation in Python?

What do I use for a max-heap implementation in Python?

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn) time.

Can we do the same by some method in O(n) time? If we can, then please tell or suggest some method.

Finding the median of an unsorted array

It seems that a priority queue is just a heap with normal queue operations like insert, delete, top, etc. Is this the correct way to interpret a priority queue? I know you can build priority queues in different ways but if I were to build a priority queue from a heap is it necessary to create a priority queue class and give instructions for building a heap and the queue operations or is it not really necessary to build the class?

What I mean is if I have a function to build a heap and functions to do operations like insert and delete, do I need to put all these functions in a class or can I just use the instructions by calling them in `main`.

I guess my question is whether having a collection of functions is equivalent to storing them in some class and using them through a class or just using the functions themselves.

What I have below is all the methods for a priority queue implementation. Is this sufficient to call it an implementation or do I need to put it in a designated priority queue class?

    #ifndef MAX_PRIORITYQ_H
    #define MAX_PRIORITYQ_H
    #include &lt;iostream&gt;
    #include &lt;deque&gt;
    #include &quot;print.h&quot;
    #include &quot;random.h&quot;

    int parent(int i)
    {
        return (i - 1) / 2;
    }

    int left(int i)
    {
        if(i == 0)
            return 1;
        else
            return 2*i;
    }

    int right(int i)
    {
        if(i == 0)
            return 2;
        else
            return 2*i + 1;
    }

    void max_heapify(std::deque&lt;int&gt; &amp;A, int i, int heapsize)
    {
        int largest;
        int l = left(i);
        int r = right(i);
        if(l &lt;= heapsize &amp;&amp; A[l] &gt; A[i])
            largest = l;
        else
            largest = i;
        if(r &lt;= heapsize &amp;&amp; A[r] &gt; A[largest])
            largest = r;
        if(largest != i) {
            exchange(A, i, largest);
            max_heapify(A, largest, heapsize);
            //int j = max_heapify(A, largest, heapsize);
            //return j;
        }
        //return i;
    }

    void build_max_heap(std::deque&lt;int&gt; &amp;A)
    {
        int heapsize = A.size() - 1;
        for(int i = (A.size() - 1) / 2; i &gt;= 0; i--)
            max_heapify(A, i, heapsize);
    }

    int heap_maximum(std::deque&lt;int&gt; &amp;A)
    {
        return A[0];
    }

    int heap_extract_max(std::deque&lt;int&gt; &amp;A, int heapsize)
    {
        if(heapsize &lt; 0)
            throw std::out_of_range(&quot;heap underflow&quot;);
        int max = A.front();
        //std::cout &lt;&lt; &quot;heapsize : &quot; &lt;&lt; heapsize &lt;&lt; std::endl;
        A[0] = A[--heapsize];
        A.pop_back();
        max_heapify(A, 0, heapsize);
        //int i = max_heapify(A, 0, heapsize);
        //A.erase(A.begin() + i);
        return max;
    }

    void heap_increase_key(std::deque&lt;int&gt; &amp;A, int i, int key)
    {
        if(key &lt; A[i])
            std::cerr &lt;&lt; &quot;New key is smaller than current key&quot; &lt;&lt; std::endl;
        else {
            A[i] = key;
            while(i &gt; 1 &amp;&amp; A[parent(i)] &lt; A[i]) {
                exchange(A, i, parent(i));
                i = parent(i);
            }
        }
    }

    void max_heap_insert(std::deque&lt;int&gt; &amp;A, int key)
    {
        int heapsize =  A.size();
        A[heapsize] = std::numeric_limits&lt;int&gt;::min();
        heap_increase_key(A, heapsize, key);
    }

Difference between priority queue and a heap

I am working on an application that demonstrates the _Djikstra&#39;s algorithm_, and to use it, I need to restore the heap property when my elements&#39; value is decreased.

The problem regarding the complexity is that **when the algorithm changes the value of an element, that element&#39;s index** in the internal structure (heap in this case) used for the priority queue **is unknown**. As such, I currently need to do an O(n) search, in order to recover the index, before I can perform an actual _decrease-key_ on it.

Moreover, I am not exactly sure about the actual code needed for the operation. I am using the D-Heap [here][1] for my Priority Queue. Pseudocode would help, but I would prefer an example in Java on how this should be done.


  [1]: http://en.algoritmy.net/article/41909/D-ary-heap

How to implement O(logn) decrease-key operation for min-heap based Priority Queue?

Python has `heapq` module which implements heap data structure and it supports some basic operations (push, pop).

How to remove i-th element from the heap in O(log n)? Is it even possible with `heapq` or do I have to use another module?

Note, there is an example at the bottom of the documentation:
http://docs.python.org/library/heapq.html
which suggest a possible approach - this is not what I want. I want the element to remove, not to merely mark as removed.

Python: delete element from heap

I understand how to delete the root node from a max heap but is the procedure for deleting a node from the middle to remove and replace the root repeatedly until the desired node is deleted?


1. Is O(log n) the optimal complexity for this procedure?

2. Does this affect the big O complexity since other nodes must be deleted in order to delete a specific node?

All Heap Solutions on Gang of Coders

Total of 21 Heap Solutions

What's the time complexity of functions in heapq library