[TOC]
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用 Insert()方法读取数据流，使用 GetMedian()方法获取当前读取数据的中位数。
public class Solution {public void Insert(Integer num) { }
public Double GetMedian() {}
}思路一：使用 partition 函数找出无序数组的中位数
从数据流中读出数据，首先需要一个容器来保存，如果采用数组作为容器，并且保存的时候直接放在数组末尾，不排序，读完之后，再通过 partition 函数从一个无序数组中寻找第 n / 2 大的数（即中位数），这里就可以借鉴“数组中出现次数超过一半的数字”那道题了
import java.util.ArrayList;
import static java.util.Collections.swap;
public class Solution {ArrayList<Integer> list = new ArrayList<>();
public void Insert(Integer num) {list.add(num);
}
public int partition(ArrayList<Integer> list,int low,int high){int base = list.get(high);
int i = low - 1;
// 注意这里 for 循环 j 的起始位置为 low
for(int j = low; j < high; j++){if(list.get(j) <= base){
i++;
swap(list,i,j);
}
}
swap(list,i+1,high);
return i+1;
}
public Double GetMedian() {
double result = 0;
int index = partition(list, 0, list.size()-1);
int middle = 0;
if((list.size() % 2) == 0) {middle = list.size() >> 1;
}else {middle = (int) Math.floor(list.size() >> 1);
}
while (index != middle){if(index > middle){index = partition(list, 0, index - 1);
}else {index = partition(list, index + 1, list.size()-1);
}
}
if(list.size() % 2 == 0 && index != 0 ){result = (list.get(index) + list.get(index - 1)) / 2.0;
}else {result = list.get(index);
}
return result;
}
}思路二：有序的插入到数组
在向数组中插入新的数据时让数组保持有序（可以采用插入排序）每插入一个数，可能需要移动 o(n)个数，对于插入 n 个数，时间复杂度为 o(n^2)
然后在排好序的数组中找出中位数，时间复杂度为 o(1)
思路三：有序的插入到链表
用链表作为保存数据流中的数据的容器，同样的，每插入一个数，需要 o(n)的时间复杂度才能找到合适的插入位置，使用链表和使用数组的时间复杂度一样
思路四：使用平衡二叉树 AVL 树保存数据
插入到 AVL 树中的时间复杂度为 o(logn)，获得中位数的时间复杂度为 o(1)
思路五：使用最大堆和最小堆分别求出两部分的最大值和最小值
具体思路
在堆中插入一个数据的时间效率为 o(logn)，得到堆顶的数据的时间复杂度为 o(1)
- 数据平均分配到两个堆中，两个堆中的数目只差不超过 1
- 保证最大堆的数据都小于最小堆的数据
依次将数据流中的数据依次放入最大堆和最小堆，当将要放入最小堆的数据小于最大堆的某些数，那么先将这个数插入最大堆中，然后取出最大堆中的最大值放入最小堆中。同理，如果将要放入最大堆的数据大于最小堆的某些数，那么就先将这个数放入最小堆中，然后取出最小堆的最小值放入最大堆
回顾堆的性质
在使用堆之前我们先来回顾一下堆的性质
1、什么是堆：堆其实就是一颗完全二叉树，除了最底层，其他层的节点都被元素填满，并且最底层尽可能从左到右填入
2、堆有哪些性质：堆一般用一维数组实现，并且该一维数组是堆的层次遍历对应的序列
1）堆的子节点和父节点之间的位置关系：对于节点 i, 它的的左右子节点在一维数组中的索引为：2i+ 1 和 2i+2
它的父节点的索引为 floor((i-1)/2)
2)堆的深度：同二叉树的深度一样为 θ（logn）
3)堆的叶节点的下标分别为：floor(n/2)，floor(n/2)+1,floor(n/2)+2,floor(n/2)+3,floor(n/2)+4…… n-1
接下来就是回顾堆排序了，堆排序是在简单选择排序的基础上演化而来的
回顾简单选择排序
所以我们先回顾一下简单选择排序
- 简单选择排序的思想：每次从剩下的数中挑选一个最小的数放在已经排好序的末尾，这个最小的数需要找到它的下标，然后和 arr[i]进行交换
简单选择排序的实现
public void simpleSort(int[] arr){for(int i = 0; i < arr.length - 1; i++){
int minIndex = i;
for(int j = i+1; j < arr.length; j++){if(arr[j] < arr[minIndex]){minIndex = j;}
}
swap(arr, i, minIndex);
}
}
public void swap(int[] arr,int i,int j){
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}从代码中我们可以看出，在每一轮比较中（从第一个 for 循环看出一共需要比较 arr.length- 1 轮）通过两两比较寻找剩下的序列中最小的数的下标，然后将 arr[i]与 arr[minIndex]交换，然后下一轮又从 i + 1 开始继续寻找剩下的序列中最小数的下标，这个过程中有的数实际上互相比较了很多次，所以这是一个非常损耗性能的事情
堆排序如何实现
假如给了我们一个数组 arr={4,8,1,0,3,5}, 我们如何通过堆排序来对该数组进行排序呢（由大到小）
步骤如下：
1）将该数组构建成一个最大堆
2）取出最大堆的根节点，维护新堆的最大堆性质，构建一个新的最大堆（堆的大小减一）
3）重复步骤 2，直到取完堆中的所有节点
最后总结一下堆排序的伪代码
大顶堆排序的具体实现 ( 内部由大到小 )： 最后将数组顺序排列
import org.omg.CORBA.RepositoryIdHelper;
import java.util.Arrays;
public class HeapSort {public static void main(String[] args){HeapSort heapSort = new HeapSort();
int[] arr = {5, 2, 7, 1, 9, 3};
//[1, 2, 3, 5, 7, 9]
heapSort.heapSort(arr);
System.out.println(Arrays.toString(arr));
}
private int heapSize = 0;
public void heapSort(int[] arr){
// 构建一个最大堆
buildMaxHeap(arr);
for(int i = arr.length-1; i > 0; i--){swap(arr,i,0);
heapSize--;
maxHeapify(arr, 0);
}
}
public void buildMaxHeap(int[] arr){
heapSize = arr.length;
// 检查除了叶子节点以外的其他节点是否满足最大堆的性质
for(int i = (arr.length >> 1) - 1; i >= 0; i--){maxHeapify(arr, i);
}
}
public void maxHeapify(int[] arr,int i){
int leftIndex = 2 * i + 1;
int rightIndex = 2 * i + 2;
int largeIndex = i;
if(leftIndex <heapSize && arr[leftIndex] > arr[i]){largeIndex = leftIndex;}
if(rightIndex < heapSize && arr[rightIndex] > arr[largeIndex]){largeIndex = rightIndex;}
if(largeIndex != i){swap(arr, largeIndex, i);
maxHeapify(arr,largeIndex);
}
}
public void swap(int[] arr,int i,int j){
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
小顶堆的实现 （* 内部实现 由小到大*）：最后将数组降序排列
import sun.net.www.HeaderParser;
import java.util.Arrays;
public class SmallHeap {public static void main(String[] args){SmallHeap smallHeap = new SmallHeap();
int[] arr = {5, 2, 7, 1, 9, 3};
///[9, 7, 5, 3, 2, 1]
smallHeap.smallHeapSort(arr);
System.out.println(Arrays.toString(arr));
}
int heapSize = 0;
public void smallHeapSort(int[] arr){buildSmallHeap(arr);
for(int i = arr.length - 1; i > 0; i--){swap(arr, i, 0);
heapSize--;
minHeapify(arr, 0);
}
}
public void swap(int[] arr,int i,int j){int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void buildSmallHeap(int[] arr){
heapSize = arr.length;
for(int i =( arr.length >> 1) - 1; i >= 0 ; i--){minHeapify(arr, i);
}
}
public void minHeapify(int[] arr,int i){
int leftIndex = 2 * i + 1;
int rightIndex = 2 * i + 2;
int minIndex = i;
if (leftIndex < heapSize && arr[leftIndex] < arr[i]) {minIndex = leftIndex;}
if (rightIndex < heapSize && arr[rightIndex] < arr[minIndex]) {minIndex = rightIndex;}
if (minIndex != i) {swap(arr,i,minIndex);
minHeapify(arr,minIndex);
}
}
}
堆的应用——优先队列
最大优先队列（最大堆）
1）insert(S,x): 把 x 插入集合 S 中
2）maximum(S): 返回 S 的最大值
3）extractMax(S)：remove 并且返回 S 的最大值
4）increaseKey(S,i,k): 将 S[i]增加到 K,
应用
作业调度，选出最高优先级的作业执行，随时 insert 一个新的作业到队列
最小优先队列（最小堆）
1）insert(S,x): 把 x 插入集合 S 中
2）minimum(S): 返回 S 的最小值
3）extractMin(S)：remove 并且返回 S 的最小值
4）decreaseKey(S,x,k): 将 S[i]减小到 K,
最大优先队列和最小优先队列的实现
本题的实现：通过最大堆和最小堆分别构建最大优先队列和最小优先队列
import java.util.ArrayList;
import static java.util.Collections.swap;
public class Solution {
class MaxHeap{ArrayList<Integer> maxHeapList = new ArrayList<Integer>();
private int maxHeapSize ;
public MaxHeap() {this.maxHeapSize = maxHeapList.size();
}
}
class MinHeap{ArrayList<Integer> minHeapList = new ArrayList<Integer>();
private int minHeapSize ;
public MinHeap() {this.minHeapSize = minHeapList.size();
}
}
private int count = 0;
public void Insert(Integer num,MaxHeap maxHeap,MinHeap minHeap){if(count == 0){maxHeap.maxHeapList.add(0,num);
maxHeap.maxHeapSize++;
}else {if(count % 2 == 0){if(num > minHeap.minHeapList.get(0)){int temp = extractiMin(minHeap);
insertMinHeap(minHeap, num);
inserMaxHeap(maxHeap, temp);
}else {inserMaxHeap(maxHeap,num);
}
}else {if(num < maxHeap.maxHeapList.get(0)){int temp = extractMax(maxHeap);
inserMaxHeap(maxHeap,num);
insertMinHeap(minHeap,temp);
}else {insertMinHeap(minHeap,num);
}
}
}
count++;
}
MaxHeap maxHeap = new MaxHeap();
MinHeap minHeap = new MinHeap();
public void Insert(Integer num) {Insert(num,maxHeap,minHeap);
}
public int extractiMin(MinHeap minHeap){if(minHeap.minHeapSize < 0) return 0;
int min = minHeap.minHeapList.get(0);
minHeap.minHeapList.remove(0);
// 注意处理 heapsize 的大小
minHeap.minHeapSize--;
minHeapify(minHeap, 0);
return min;
}
// 这里维护最小堆的性质和最大堆不同，比较的是和父节点的大小，因为这里不断的插入新的节点到末尾，应该是和前面的父节点比较
public void minHeapify(MinHeap minHeap,int i){
int minIndex = i;
int parentIndex = (int) Math.floor((i - 1) / 2.0);
if(parentIndex >= 0 && minHeap.minHeapList.get(i) < minHeap.minHeapList.get(parentIndex) ){
minIndex = parentIndex;
swap(minHeap.minHeapList, i, minIndex);
minHeapify(minHeap,minIndex);
}
}
public void insertMinHeap(MinHeap minHeap,int num){
minHeap.minHeapSize++;
minHeap.minHeapList.add(minHeap.minHeapSize - 1,Integer.MAX_VALUE);
decreaseKey(minHeap.minHeapList, minHeap.minHeapSize - 1, num);
}
public void decreaseKey(ArrayList<Integer> list,int i,int key){if(list.get(i) < key)return;
list.remove(i);
list.add(i, key);
minHeapify(minHeap,i);
}
public void inserMaxHeap(MaxHeap maxHeap,int num){
maxHeap.maxHeapSize++;
if(maxHeap.maxHeapSize > 0) {maxHeap.maxHeapList.add(maxHeap.maxHeapSize - 1, Integer.MIN_VALUE);
}else {maxHeap.maxHeapList.add(0,Integer.MAX_VALUE);
}
increaseKey(maxHeap, maxHeap.maxHeapSize - 1, num);
}
public void increaseKey(MaxHeap maxHeap,int i,int key){if(maxHeap.maxHeapList.get(i) > key)return;
maxHeap.maxHeapList.remove(i);
maxHeap.maxHeapList.add(i, key);
while (i > 0 && maxHeap.maxHeapList.get((int) Math.floor((i-1)/2.0)) < maxHeap.maxHeapList.get(i)){swap(maxHeap.maxHeapList,i,(int) Math.floor((i-1)/2.0));
i = (int) Math.floor((i - 1) / 2.0);
}
}
public int extractMax(MaxHeap maxHeap){if(maxHeap.maxHeapSize < 0)return 0;
int max = maxHeap.maxHeapList.get(0);
maxHeap.maxHeapList.remove(0);
maxHeap.maxHeapSize--;
maxHeapify(maxHeap, 0);
return max;
}
public void maxHeapify(MaxHeap maxHeap,int i){
int leftIndex = 2 * i +1;
int rightIndex = 2 * i +2;
int largeIndex = i;
if(leftIndex < maxHeap.maxHeapSize && maxHeap.maxHeapList.get(leftIndex) > maxHeap.maxHeapList.get(i)){largeIndex = leftIndex;}
if(rightIndex < maxHeap.maxHeapSize && maxHeap.maxHeapList.get(rightIndex) > maxHeap.maxHeapList.get(largeIndex)){largeIndex = rightIndex;}
if(largeIndex != i){swap(maxHeap.maxHeapList,i,largeIndex);
maxHeapify(maxHeap,largeIndex);
}
}
public Double GetMedian() {if(count % 2 == 0){return (maxHeap.maxHeapList.get(0) + minHeap.minHeapList.get(0)) / 2.0;
}else {return (double)maxHeap.maxHeapList.get(0);
}
}
}该题的实现：基于现有的类库：PriorityQueue 实现最大堆和最小堆
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
private int count = 0;
// 默认升序排列，也就是默认为最小堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 通过重写 Comparator 接口的 compare 方法，构建一个逆序排列的最大堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {return o2 - o1;}
});
public void Insert(Integer num) {if (count %2 == 0) {
// 最大堆插入一个元素之后，内部会自动重新构建一个最大堆 maxheapify
maxHeap.offer(num);
//remove 并返回第一个元素
int temp = maxHeap.poll();
// 插入到最小堆，内部同样进行 minheapify
minHeap.offer(temp);
} else {minHeap.offer(num);
int temp = minHeap.poll();
maxHeap.offer(temp);
}
count++;
}
public Double GetMedian() {if (count %2 == 0) {return new Double((minHeap.peek() + maxHeap.peek())) / 2;
} else {return new Double(minHeap.peek());
}
}
}参考
《剑指 offer 纪念版》
《算法导论第三版》