Heap && PriorityQueue: repeatly find the maximum/minmum

[YuezhenQin]

A heap is a data structure that is an implementation of the priority queue. In a priority queue, elements with high priority are served before elements with low priority.

A heap is a container that stores elements, and supports the following operations:

• add() in O(logn)
• removeMin() in O(logn)
• findMin in O(1)

[YuezhenQin]

How is a heap implemented?

There are multiple ways to implement a heap, although the most popular way is called a binary heap using an array. A binary heap implements a binary tree, but with only an array.

The parent-child relationships are done using math with the indices. The first element at index 0 is the root, then the elements at indices 1 and 2 are the root's children, the elements at indices 3 and 4 are the children of the element at index 1 and the elements at indices 5 and 6 are the children of the element at index 2, and so on. If a node is at index i, then its children are at indices 2i + 1 and 2i + 2. When elements are added or removed, operations are done to maintain the aforementioned property of parent.val <= child.val. The number of operations needed scales logarithmically with the number of elements in the heap, and the process is known as "bubbling up".

What is the fastest an arbitrary array can be converted into a heap? O(n)

[YuezhenQin]

A heap is an amazing tool whenever you need to repeatedly find the maximum or minimum element. Let's look at some example problems.

In many problems, using a heap can improve an algorithm's time complexity from O(n²) to O(n⋅logn), which is a massive improvement.