[Algo] heap, max heap, min heap priority_queue

 堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

能保证取max/min是O(1)时间。通常如果查最小值/最大值，我们可以用Heap。

cpp impl:

https://www.geeksforgeeks.org/binary-heap/

top -> return max/min  : O(1) 

• impl : take first element in the array

push->insert new element : O(logN)

• impl: 
• push back the element, the last index will be i
• do a while loop to compare i element and parent of i element
• if parent is bigger / smaller 
• do a swap
• if not, break and all good
• how to get parent index of i element: 
• (i-1)/2

// Inserts a new key 'k'

void MinHeap::insertKey(int k)

{

    if (heap_size == capacity)

    {

        cout << "\nOverflow: Could not insertKey\n";

        return;

    }

  

    // First insert the new key at the end

    heap_size++;

    int i = heap_size - 1;

    harr[i] = k;

  

    // Fix the min heap property if it is violated

    while (i != 0 && harr[parent(i)] > harr[i])

    {

       swap(&harr[i], &harr[parent(i)]);

       i = parent(i);

    }

}

pop->remove the  top element : O(logN)

• remove top
• put last element to the top
• MinHeapify
• from top then recusivly call

void MinHeap::MinHeapify(int i)

{

    int l = leftChild(i); //(2*i + 1)

    int r = rightChild(i); //(2*i + 2)

    int smallest = i;

    if (l < heap_size && harr[l] < harr[i])

        smallest = l;

    if (r < heap_size && harr[r] < harr[smallest])

        smallest = r;

    if (smallest != i)

    {

        swap(&harr[i], &harr[smallest]);

        MinHeapify(smallest);

    }

}   

make_heap : construct a heap from n element:

• solution 1 : insert one by one O(n*logn)
• solution 2 : from last element to execute Heapify(A, i) -> O(n)
• Build-Max-Heap^[1] (A):
   heap_length[A] ← length[A]
   for i ← floor(length[A]/2) downto 1 do
   Max-Heapify(A, i)
• at level h (down to up), we have 2^(H -h+1) nodes, H = logn+1
• all these nodes should be Heapify with a complexity of O(h)
• so the whole complexity is:  sumLevels[ 2^(H -h+1)  * O(logh)] 

merge heap : put one then after, then do a construct heap : O(log(N +M))

priority_queue

本质上就是一个包装成queue 的heap，by default 是一个max_heap。

C++ STL priority_queue is a template, if by default, it's a vector with max_heap operations who offer interface as : queue.

https://blog.csdn.net/roufoo/article/details/80638476

https://blog.csdn.net/qq_39463274/article/details/105414188?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.opensearchhbase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.opensearchhbase

https://www.geeksforgeeks.org/priority-queue-set-1-introduction/

https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/