Binary Heap

Binary Heap is an important data structure which can be used to implement priority queue. Two types of binary heap are commonly seen: min-heap and max-heap. A binary heap has two properties:

• Shape property: the heap should be a full binary tree (can be denoted as an array)
• heap property: children should be smaller (bigger) than parent

When inserting an element into heap, we insert from bottom (leaf). Then we check if the two properties hold, otherwise we swap parent and child. When removing an element from heap (always from root), we use the last element at the last level to replace root, then we adjust heap. So,

• The time complexity of insertion is O(logN)
• The time complexity of removal is O(logN)
• The time complexity of building a heap can be O(N)

With binary heap, a K-way merge can be done in O(N*logK), naive ways take O(N*K). Besides, we also have min-max heap which can insert remove the min and max element in O(logN). Basically, it is a mixed heap with odd level to be min heap and even level to be max heap.