05-20-2014, 03:36 PM
Max-heaps
We define a max-heap as a heap that satisfies the property that A[PARENT(i)] ≥ A[i] for all i, i.e. the value of every parent is greater than both children. Thus for a max-heap, the largest value is stored at the root.
Creating a max-heap
Building a max-heap from an array involves two routines
MAX-HEAPIFY(A,i) - maintains the max-heap property by assuming that the branches of the binary tree rooted at the children of node i are max-heaps but that node i may be smaller than either (or both) of its children. Thus it percolates node i down through the max-heap such that the branch starting at node i is a max-heap.
BUILD-MAX-HEAP(A) - creates a max-heap from an array by calling MAX_HEAPIFY() from the "bottom up" of the array (such that at each step the bottom branches are max-heaps).
We define a max-heap as a heap that satisfies the property that A[PARENT(i)] ≥ A[i] for all i, i.e. the value of every parent is greater than both children. Thus for a max-heap, the largest value is stored at the root.
Creating a max-heap
Building a max-heap from an array involves two routines
MAX-HEAPIFY(A,i) - maintains the max-heap property by assuming that the branches of the binary tree rooted at the children of node i are max-heaps but that node i may be smaller than either (or both) of its children. Thus it percolates node i down through the max-heap such that the branch starting at node i is a max-heap.
BUILD-MAX-HEAP(A) - creates a max-heap from an array by calling MAX_HEAPIFY() from the "bottom up" of the array (such that at each step the bottom branches are max-heaps).