Heap

Properties

• order property - key of every node >= the key of its children (for max heap)
• shape property - binary tree and every level completely filled, except the last level which filled from left to right

Operations

• heapify - O(n) (a coarse analysis is O(nlgn), but it's not)
• extractMax - O(lgn)
• insertion - O(lgn)

Others

• a concrete data structure to implement Priority Queue
• designed for finding max / min
• NOT for searching

Application

• Heapsort - O(nlgn) without extra space
• Line segment intersections
• MST (Minimum Spanning Tree) Algorithm (Prim / Kruskal)
• Kth smallest elements - O(n) + O(klgk)

Reference

• Priority Queues
• Heapsort