// maxHeap.cpp : Defines the entry point for the console application. // #include "stdafx.h" #define LENGTH(x) (sizeof(x)/sizeof(x[0])) static int heap_size = 0; int parent(int i){ return (i)/2; } int left(int i) { return 2*(i); } int right(int i) { return 2*(i)+1; } void maxHeapify(int A[], int i) { int largest; int l, r, tmpdata; l = left(i); r = right(i); if (l < heap_size && A[l] > A[i]) largest = l; else largest = i; if (r < heap_size && A[r] > A[largest]) largest = r; if (largest != i) { tmpdata = A[i]; A[i] = A[largest]; A[largest] = tmpdata; maxHeapify(A, largest); } } void buildMaxHeap(int A[], int len) { int i; heap_size = len; for (i = (len)/2; i > 0; i--) maxHeapify(A, i); } inline void dumpHeap(int A[], int len) { int i; for (i = 0; i < len; i++) printf("%4d", A[i]); printf("/n"); } int main(int argc, char* argv[]) { int A[] = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; printf("heap size:%d/n", LENGTH(A)); dumpHeap(A, LENGTH(A)); buildMaxHeap(A, LENGTH(A)); dumpHeap(A, LENGTH(A)); return 0; }
下标为largest的节点在交换后的值为A[i],以该节点为根的子树又有可能违反最大堆的性质，因而要递归子树调用maxHeapify.
