Push, Pop & Heapify - Step through each line of code
Insert a new element at the end of the array (maintaining the structure property), then percolate it up by swapping with its parent until the heap-order property is restored.
Remove the root (min element), move the last element to the root position, then percolate it down by swapping with the smaller child until heap-order is restored.
Build a heap from an unordered array in O(n) by copying elements in (structure property only), then calling PercolateDown on each non-leaf node from bottom to top.
Two approaches to building a heap. $N = 15$, $h = \lfloor\log_2 N\rfloor = 3$.
Insert elements one by one. Each element percolates up. Cost = depth from root.
Total complexity for $N$ items:
$$\sum_{h=0}^{\log N} 2^h \times O(h) \;=\; O\!\left(\sum_{h=0}^{\log N} 2^h \cdot h\right)$$ $$= O\!\left(2^{\log N} \cdot \log N\right) = \color{#e74c3c}{O(N \log N)}$$Most nodes are at the bottom, and each pays the highest cost. Suboptimal!
Copy all elements in, then percolate down from last non-leaf. Cost = height above leaves.
Total complexity for $N$ items:
$$\sum_{h=0}^{\log N} \frac{N}{2^h} \times O(h) \;=\; O\!\left(N \sum_{h=0}^{\log N} \frac{h}{2^h}\right)$$ $$\leq O\!\left(N \cdot \sum_{h=0}^{\infty} \frac{h}{2^h}\right) = \color{#27ae60}{O(N)}$$Most nodes are at the bottom, but each pays the lowest cost ($O(0)$). Optimal!
Key Intuition: In both cases, $\sim N/2$ nodes sit at the bottom. Naive makes them pay $O(\log N)$ each (percolate up the full height). Floyd's makes them pay $O(0)$ each (leaves need no percolation). The few nodes at the top that pay high cost are exponentially fewer in number.