<span class="line"><span style="color: #D8DEE9FF">#</span><span style="color: #D8DEE9">include</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9">iostream</span><span style="color: #81A1C1">></span></span>
<span class="line"><span style="color: #D8DEE9FF">#</span><span style="color: #D8DEE9">include</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9">vector</span><span style="color: #81A1C1">></span></span>
<span class="line"></span>
<span class="line"><span style="color: #81A1C1">using</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">std</span><span style="color: #81A1C1">::</span><span style="color: #D8DEE9FF">vector</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #81A1C1">using</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">std</span><span style="color: #81A1C1">::</span><span style="color: #D8DEE9FF">cout</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #81A1C1">using</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">std</span><span style="color: #81A1C1">::</span><span style="color: #D8DEE9FF">swap</span><span style="color: #81A1C1">;</span></span>
<span class="line"></span>
<span class="line"><span style="color: #81A1C1">void</span><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">Heapify</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">vector</span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9">int</span><span style="color: #81A1C1">>&</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF">)</span><span style="color: #ECEFF4">{</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #616E88">// Initialize largest as root</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">left</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">2</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">*</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">+</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">1</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #616E88">// Left child</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">right</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">2</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">*</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">+</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">2</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #616E88">// Right child</span></span>
<span class="line"></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// If left child is larger than root</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">if</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">left</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">&&</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">left</span><span style="color: #D8DEE9FF">] </span><span style="color: #81A1C1">></span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF">]) </span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">left</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// If right child is larger than largest so far</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">if</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">right</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">&&</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">right</span><span style="color: #D8DEE9FF">] </span><span style="color: #81A1C1">></span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF">]) </span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">right</span><span style="color: #81A1C1">;</span></span>
<span class="line"></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// If largest is not root</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">if</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">!=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF">)</span><span style="color: #ECEFF4">{</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">swap</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF">]</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF">])</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// Recursively heapify the affected sub-tree</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">Heapify</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">largest</span><span style="color: #D8DEE9FF">)</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">}</span></span>
<span class="line"><span style="color: #ECEFF4">}</span></span>
<span class="line"></span>
<span class="line"><span style="color: #81A1C1">void</span><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">HeapSort</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">vector</span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9">int</span><span style="color: #81A1C1">>&</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">)</span><span style="color: #ECEFF4">{</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #ECEFF4">.</span><span style="color: #88C0D0">size</span><span style="color: #D8DEE9FF">()</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// build max heap</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// The parent of the ith element is at index i / 2 - 1.</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// Therefore, the parent of the nth element is at index n / 2 - 1</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">for</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">/</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">2</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">-</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">1</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">>=</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">0</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #81A1C1">--</span><span style="color: #D8DEE9FF">) </span><span style="color: #88C0D0">Heapify</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF">)</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// One by one extract an element from heap</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">for</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">n</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">-</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">1</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">></span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">0</span><span style="color: #81A1C1">;</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #81A1C1">--</span><span style="color: #D8DEE9FF">)</span><span style="color: #ECEFF4">{</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// Move current root to end</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">swap</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #B48EAD">0</span><span style="color: #D8DEE9FF">]</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">[</span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF">])</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4"> </span><span style="color: #616E88">// Call max heapify on the reduced heap (re-build max heap)</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">Heapify</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">0</span><span style="color: #D8DEE9FF">)</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">}</span></span>
<span class="line"><span style="color: #ECEFF4">}</span></span>
<span class="line"></span>
<span class="line"><span style="color: #81A1C1">void</span><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">PrintArray</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">const</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">vector</span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9">int</span><span style="color: #81A1C1">>&</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">)</span><span style="color: #ECEFF4">{</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">for</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> : </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">)</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">cout</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><<</span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">i</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><<</span><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">"</span><span style="color: #A3BE8C"> </span><span style="color: #ECEFF4">"</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">cout</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><<</span><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">"</span><span style="color: #EBCB8B">\n</span><span style="color: #ECEFF4">"</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4">}</span></span>
<span class="line"></span>
<span class="line"><span style="color: #D8DEE9">int</span><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">main</span><span style="color: #D8DEE9FF">()</span><span style="color: #ECEFF4">{</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">vector</span><span style="color: #81A1C1"><</span><span style="color: #D8DEE9">int</span><span style="color: #81A1C1">></span><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">=</span><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">{</span><span style="color: #B48EAD">4</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">6</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">8</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">5</span><span style="color: #ECEFF4">,</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">9</span><span style="color: #ECEFF4">}</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">cout</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><<</span><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">"</span><span style="color: #A3BE8C">Original Array:</span><span style="color: #EBCB8B">\n</span><span style="color: #ECEFF4">"</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">PrintArray</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">)</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">HeapSort</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">)</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #D8DEE9">cout</span><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1"><<</span><span style="color: #D8DEE9FF"> </span><span style="color: #ECEFF4">"</span><span style="color: #A3BE8C">Sorted Array:</span><span style="color: #EBCB8B">\n</span><span style="color: #ECEFF4">"</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #88C0D0">PrintArray</span><span style="color: #D8DEE9FF">(</span><span style="color: #D8DEE9">arr</span><span style="color: #D8DEE9FF">)</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #D8DEE9FF"> </span><span style="color: #81A1C1">return</span><span style="color: #D8DEE9FF"> </span><span style="color: #B48EAD">0</span><span style="color: #81A1C1">;</span></span>
<span class="line"><span style="color: #ECEFF4">}</span></span>
A max-heap viewed as (a) a binary tree and (b) an arry. The root of the tree is A[1], and given the index i of a node, there’s a simple way to compute the indices of it’s parent, left child, and right child with the one-line procedures PARENT, LEFT, and RIGHT:
PARENT(i): $$\left \lfloor i / 2 \right \rfloor$$
LEFT(i): $$\left \lfloor 2i \right \rfloor$$
RIGHT(i): $$\left \lfloor 2i + 1 \right \rfloor$$
There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satify a heap property, the specifics of which depend on the kind of heap. In max-heap, the max-heap property is that for every node i other than the root
A[PARENT(i)] >= A[i]
that is, the value of a node is at most the value of its parent. Thus, the largest value in a max-heap is stored at the root, the subtree rooted at a node contains values no larger than that contained at the node itself. A min-heap is organized in the opposite way: the min-heap property is that for every node i other than the root,
A[PARENT(i)] <= A[i]
MAX-HEAPIFY:
The action of MAX-HEAPIFY(A, 2), where, A.heap-size = 10.
BUILD-MAX-HEAP
The operation of BUILD-MAX-HEAP, showing the data structure before the call to MAX-HEAPIFY in line 3 of BUILD-MAX-HEAP.