堆结构：
- 堆结构就是用数组实现的完全二叉树结构
- 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆。
- 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆。
堆排序思路：
1，先让整个数组都变成大根堆结构，建立堆的过程: （heapInsert）
1)从上到下的方法，时间复杂度为O(NlogN)
2)从下到上的方法，时间复杂度为O(N)
2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调 整堆，一直周而复始，时间复杂度为O(NlogN)
(heapify)
3，堆的大小减小成0之后，排序完成
堆排序的时间复杂度：HeapInsert和Haepify过程的时间复杂度都为O(N lgN)，因此，堆排序的时间复杂度为O(N lgN)，额外空间复杂度为O（1）。
扩展题：
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元 素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的 排序算法针对这个数据进行排序。
思路：
- 前k个数，可以使用堆排序将最小的值的位置确定，将其放置在0位置。
- 依次往后移动大小为k的堆排序，每次可以确定一个值的位置。
tips：
- 这里可以使用java自带的PriorityQueue（优先队列，不往里加任何参数的话，默认实现小根堆功能）类，该类会将加进去的元素自动排成小根堆，
小根堆每次排序的代价为lgK，所以排序的代价为O(N lgK)， - 该类底层用一个数组放置堆的内容，当没有固定数组的大小时，还会随着加入数据的数量自动成倍扩容，如，长度为1，扩容为2,2不够用，扩容为4；扩容的代价为：
扩容的次数为lgN，每次的代价为N（移动N次），扩容的期望为O（lgN）。 - 系统提供的堆结构只能按人给的顺序排序，不能满足修改已经输入的数据，等等。想要实现比较细粒度的功能需要自己手写堆排序，
堆的应用
一个数据流中，随时取得中位数。
- 初始化一个大根堆，初始化一个小根堆
- 第一个数字入大根堆
- 循环：当前数字是否小于等于大根堆堆顶，是，入大根堆，否入小根堆
- 比较两个堆的大小，如果较多的堆个数比较少的堆大2，较多的堆弹出堆顶，进较小的堆
public class Code06_MadianQuick {
public static class MedianHolder {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());
private void modifyTwoHeapsSize() {
if (this.maxHeap.size() == this.minHeap.size() + 2) {
this.minHeap.add(this.maxHeap.poll());
}
if (this.minHeap.size() == this.maxHeap.size() + 2) {
this.maxHeap.add(this.minHeap.poll());
}
}
public void addNumber(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyTwoHeapsSize();
}
public Integer getMedian() {
int maxHeapSize = this.maxHeap.size();
int minHeapSize = this.minHeap.size();
if (maxHeapSize + minHeapSize == 0) {
return null;
}
Integer maxHeapHead = this.maxHeap.peek();
Integer minHeapHead = this.minHeap.peek();
if (((maxHeapSize + minHeapSize) & 1) == 0) {
return (maxHeapHead + minHeapHead) / 2;
}
return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
}
}
public static class MaxHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if (o2 > o1) {
return 1;
} else {
return -1;
}
}
}
public static class MinHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if (o2 < o1) {
return 1;
} else {
return -1;
}
}
}
// for test
public static int[] getRandomArray(int maxLen, int maxValue) {
int[] res = new int[(int) (Math.random() * maxLen) + 1];
for (int i = 0; i != res.length; i++) {
res[i] = (int) (Math.random() * maxValue);
}
return res;
}
// for test, this method is ineffective but absolutely right
public static int getMedianOfArray(int[] arr) {
int[] newArr = Arrays.copyOf(arr, arr.length);
Arrays.sort(newArr);
int mid = (newArr.length - 1) / 2;
if ((newArr.length & 1) == 0) {
return (newArr[mid] + newArr[mid + 1]) / 2;
} else {
return newArr[mid];
}
}
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
boolean err = false;
int testTimes = 200000;
for (int i = 0; i != testTimes; i++) {
int len = 30;
int maxValue = 1000;
int[] arr = getRandomArray(len, maxValue);
MedianHolder medianHold = new MedianHolder();
for (int j = 0; j != arr.length; j++) {
medianHold.addNumber(arr[j]);
}
if (medianHold.getMedian() != getMedianOfArray(arr)) {
err = true;
printArray(arr);
break;
}
}
System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");
}
}
