用数组来存储堆，下标为i的结点，父节点的编号为（i-1）/2，子结点的编号为2*i+1， 2*i+2。 建立堆：每次插入一个元素并调整堆的过程。 插入一个元素：插入到数组最后，更新树。 删除一个元素：删除发生在nums[0]，将最后一个元素调整到nums[0]处，更新树。 长度为len的数组，最后一个叶子节点的父节点的编号为len/2 -1。
堆的插入 只能插入到堆的最后。
void minHeapFixup(int a[], int i) {//i is the position to be insert int tmp; for (int j = (i - 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i - 1) / 2){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } void minHeapAddNumber(int a[], int n, int nNum) { a[n] = nNum; minHeapFixup(a, n); }堆的删除 只能删除第0个元素。
void minHeapFixdown(int a[], int i, int n) { int j = 2 * i + 1; int temp = a[i]; while (j < n) { if (j + 1 < n && a[j + 1] < a[j]) j++; if (a[j] >= temp) break; a[i] = a[j]; i = j; j = 2 * i + 1; } a[i] = temp; } void minHeapDeleteNumber(int a[], int n) { int tmp = a[0]; a[0] = a[n-1]; a[n-1] = tmp; minHeapFixdown(a, 0, n - 1); }堆排序
private void minHeapSort(int[] nums) { int i; int len = nums.length; for(i = len/2-1; i >= 0; i--){ adjustMinHeap(nums, i, len -1); } for(i = len-1; i >= 0; i--){ int tmp = nums[0]; nums[0] = nums[i]; nums[i] = tmp; adjustMinHeap(nums, 0, i - 1); } } private void adjustMinHeap(int[] nums, int pos, int len){ int temp; int child; for(temp = nums[pos]; 2 * pos + 1 <= len; pos = child){ child = pos * 2 + 1; if(child < len && nums[child] > nums[child + 1]){ child++; } if(nums[child] < temp){ nums[pos] = nums[child]; }else{ break; } } nums[pos] = temp; }