# Exercise 6.2.5

The code for

`MAX-HEAPIFY`

is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient`MAX-HEAPIFY`

that uses an iterative control construct (a loop) instead of recursion.

As always, the most fun was converting from 1- to 0-based indexing.

### C code

#define PARENT(i) ((i - 1) / 2) #define LEFT(i) (2 * i + 1) #define RIGHT(i) (2 * i + 2) typedef struct { int *nodes; int length; int heap_size; } heap; void max_heapify(heap A, int i) { int left, right, largest, temp; while(1) { left = LEFT(i); right = RIGHT(i); if (left < A.heap_size && A.nodes[left] > A.nodes[i]) largest = left; else largest = i; if (right < A.heap_size && A.nodes[right] > A.nodes[largest]) largest = right; if (largest == i) return; temp = A.nodes[i]; A.nodes[i] = A.nodes[largest]; A.nodes[largest] = temp; i = largest; } }