public class MaxBinarySortHeap {private transient int size;private transient List<Integer> maxRootHeap;private transient Map<Integer, Integer> equivalientStatisticsMap;public MaxBinarySortHeap() {this.size = 0;this.maxRootHeap = new ArrayList<Integer>();this.equivalientStatisticsMap = new HashMap<Integer, Integer>();}public int size() {return size;}public int[] getHeapSequence() {int[] resultArray = new int[maxRootHeap.size()];int index = 0;for (Integer element : maxRootHeap) {resultArray[index ++] = element;}return resultArray;}public void build(int[] array) {maxRootHeap.clear();equivalientStatisticsMap.clear();size = 0;for (int i = 0; i < array.length; i++) {add(array[i]);}}public void add(int element) {size ++;if (!(maxRootHeap != null && maxRootHeap.contains(element))) {maxRootHeap.add(element);int index = maxRootHeap.size() - 1;while (index > 0 && maxRootHeap.get(index) > maxRootHeap.get((index - 1) / 2)) {Util.swap(maxRootHeap, index, (index - 1) / 2);index = (index - 1) / 2;}} else {if (equivalientStatisticsMap.containsKey(element)) {equivalientStatisticsMap.put(element, equivalientStatisticsMap.get(element) + 1);} else {equivalientStatisticsMap.put(element, 1);}}}public boolean delete(int element) {if (!(maxRootHeap != null && maxRootHeap.contains(element))) {return false;} else {size --;if (equivalientStatisticsMap.containsKey(element)) {size -= equivalientStatisticsMap.get(element);equivalientStatisticsMap.remove(element);}int index = Util.getIndexByElement(maxRootHeap, element);if (index == maxRootHeap.size() - 1) {maxRootHeap.remove(index);return true;} else if (index * 2 + 1 >= maxRootHeap.size() && index * 2 + 2 >= maxRootHeap.size()) {Util.swap(maxRootHeap, index, maxRootHeap.size() - 1);maxRootHeap.remove(maxRootHeap.size() - 1);innerMaxRootHeapAdjuster(maxRootHeap, index);return true;} else {while (index * 2 + 1 < maxRootHeap.size()) {if (index * 2 + 2 < maxRootHeap.size()) {if (maxRootHeap.get(index * 2 + 1) > maxRootHeap.get(index * 2 + 2)) {Util.swap(maxRootHeap, index, index * 2 + 1);index = index * 2 + 1;} else {Util.swap(maxRootHeap, index, index * 2 + 2);index = index * 2 + 2;}} else {Util.swap(maxRootHeap, index, index * 2 + 1);maxRootHeap.remove(index * 2 + 1);return true;}}Util.swap(maxRootHeap, index, maxRootHeap.size() - 1);maxRootHeap.remove(maxRootHeap.size() - 1);innerMaxRootHeapAdjuster(maxRootHeap, index);return true;}}}public int[] sort() {int[] resultArray = new int[size];if (maxRootHeap.size() <= 2) {int index = 0;for (Integer element : maxRootHeap) {resultArray[index ++] = element;if (equivalientStatisticsMap.containsKey(element)) {int temp = equivalientStatisticsMap.get(element);while (temp -- > 0) {resultArray[index ++] = element;}}}return resultArray;} else {List<Integer> tempList = new ArrayList<Integer>(maxRootHeap.size());for (Integer element : maxRootHeap) {tempList.add(element);}int index = 0;for (int i = 0; i < maxRootHeap.size(); i ++) {maxRootHeapSortingAdjuster(maxRootHeap, i);resultArray[index ++] = maxRootHeap.get(i);if (equivalientStatisticsMap.containsKey(maxRootHeap.get(i))) {int temp = equivalientStatisticsMap.get(maxRootHeap.get(i));while (temp -- > 0) {resultArray[index ++] = maxRootHeap.get(i);}}}maxRootHeap = tempList;return resultArray;}}/** According to the given index of the element which destory the max root heap's structure,* adjust the sequence to a max root heap.* * Note : the given index must be of an element which is a leaf node of the complete binary tree.*/private void innerMaxRootHeapAdjuster(List<Integer> list, int index) {while (index != 0) {if (list.get(index) > list.get((index - 1) / 2)) {Util.swap(list, index, (index - 1) / 2);index = (index - 1) / 2;} else {break;}}}private void maxRootHeapSortingAdjuster(List<Integer> list, int fromIndex) {list.add(fromIndex, list.get(list.size() - 1));list.remove(list.size() - 1);int index = 0;while (index * 2 + 1 + fromIndex < list.size()) {if (index * 2 + 2 + fromIndex < list.size()) {if (list.get(index * 2 + 1 + fromIndex) > list.get(index * 2 + 2 + fromIndex)) {if (list.get(index + fromIndex) < list.get(index * 2 + 1 + fromIndex)) {Util.swap(list, index + fromIndex, index * 2 + 1 + fromIndex);index = index * 2 + 1;} else {break;}} else {if (list.get(index + fromIndex) < list.get(index * 2 + 2 + fromIndex)) {Util.swap(list, index + fromIndex, index * 2 + 2 + fromIndex);index = index * 2 + 2;} else {break;}}} else {if (list.get(index + fromIndex) < list.get(index * 2 + 1 + fromIndex)) {Util.swap(list, index + fromIndex, index * 2 + 1 + fromIndex);index = index * 2 + 1;} else {break;}}}}}