public class MaxHeap { public static void main(String args[]) { new MaxHeap(); } private int MaxHeapSize; public MaxHeap(){ int[] data = { 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -1 ,-1}; // System.out.println(5/2); // int[] data = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, }; MaxHeapSize=data.length-1; revise(data); print(data); // System.out.println((int) (Math.log(data.length) / Math.log(2))); // System.out.println(Math.pow(2, 2)); // maxHeapify(data, 10); buildHeap(data); // heapSort(data); // System.out.println(HeapExtractMax(data)); // heapIncreaseKey(data,30,66); MaxHeapInsert(data,77); print(data); } /*public static void print3(int[] data) { for (int i = 0; i < data.length / 2 + 2; i++) System.out.print(" "); for (int i = 1, j = 1; i < data.length; i++) { System.out.print(data[i] + " "); if (data[i] < 10) { System.out.print(" "); } else { System.out.print(" "); } if (i == j) { System.out.println(); j = 2 * j + 1; for (int v = data.length / 2 - i; v >= 0; v--) { System.out.print(" "); } } } System.out.println(); }
public static void print2(int[] data) { int i, n1, n2; int height = (int) (Math.log(data.length) / Math.log(2)); int width = (int) Math.pow(2, height); boolean firstOneOfLine = true; for (i = 1, n1 = 1, n2 = 1; i < data.length; i++) { * if (i == n1) { for (int v = 1; v < Math.pow(2, height); v++) { * System.out.print(" "); } height--; n1 = n1 * 2; } if (firstOneOfLine) { for (int v = 1; v < width; v++) { System.out.print(" "); } firstOneOfLine = false; } else { for (int v = 1; v < width * 2; v++) { System.out.print(" "); } }
System.out.print(data[i] + " "); if (data[i] < 10) { System.out.print(" "); } else { System.out.print(" "); }
if (i == n2) { System.out.println(); System.out.println(); System.out.println(); n2 = 2 * n2 + 1; width = width / 2; firstOneOfLine = true; } } }*/
public static void print(int[] data) { int i, n1, n2; int height = (int) (Math.log(data.length) / Math.log(2)); int width = (int) Math.pow(2, height); boolean firstOneOfLine = true; for (i = 1, n1 = 1, n2 = 1; i < data.length; i++) { /* * if (i == n1) { for (int v = 1; v < Math.pow(2, height); v++) { * System.out.print(" "); } height--; n1 = n1 * 2; } */ if (firstOneOfLine) { for (int v = 1; v < width; v++) { System.out.print(" "); } firstOneOfLine = false; } else { for (int v = 1; v < width * 2; v++) { System.out.print(" "); } }
System.out.print(data[i]); if (data[i] < 10) { System.out.print(" "); } else { System.out.print(" "); }
if (i == n2) { System.out.println(); n2 = 2 * n2 + 1; width = width / 2; firstOneOfLine = true; } } System.out.println(); }
public void maxHeapify(int[] A, int i) { int l = 2 * i; int r = 2 * i + 1; int large = i; int temp; if (l < MaxHeapSize && A[i] < A[l]) { large = l; } else { large = i; } if (r < MaxHeapSize && A[large] < A[r]) { large = r; } if (large != i) { temp = A[i]; A[i] = A[large]; A[large] = temp; maxHeapify(A, large); } }
public void revise(int[] A) { int temp; for (int i = 0; i <= MaxHeapSize / 2; i++) { temp = A[i]; A[i] = A[MaxHeapSize - i - 1]; A[MaxHeapSize - i - 1] = temp; } }
public void buildHeap(int[] A) { for (int i = A[A.length / 2]; i >= 1; i--) { maxHeapify(A, i); } } public void heapSort(int[] A){ int temp; buildHeap(A); for(int i=A.length-1;i>=1;i--){ temp=A[1]; A[1]=A[i]; A[i]=temp; MaxHeapSize--; maxHeapify(A,1); } } public int HeapExtractMax(int[] A){ int max; if(MaxHeapSize<1){ return -1; } max=A[1]; MaxHeapSize--; A[1]=A[MaxHeapSize]; maxHeapify(A,1); return max; } public void heapIncreaseKey(int[] A,int i,int key){ int temp; if(key<A[i]) return; A[i]=key; while(A[i/2]<A[i] && i>1){ temp=A[i/2]; A[i/2]=A[i]; A[i]=temp; i=i/2; } } public void MaxHeapInsert(int[] A,int key){ MaxHeapSize++; A[MaxHeapSize-1]=-1; heapIncreaseKey(A,MaxHeapSize-1,key); } }
