针对动态数据,求排序后处于中间的数据
思路:维护两个堆,一个大顶堆,一个小顶堆。大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆中的数据都大于大顶堆中的数据。如果有 n 个数据,n 是偶数,从小到大排序,那前 n/2 个数据存储在大顶堆中,后 n/2个数据存储在小顶堆中。这样,大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数,情况是类似的,大顶堆就存储 n/2+1 个数据,小顶堆中就存储 n/2 个数据。
//数据数组
private int[] data = new int[10];
//数据大小
private int size;
//大顶堆数据数组
private int[] bigHeap = new int[5];
//大顶堆数据大小
private int bigHeapSize;
//小顶堆数据数组
private int[] smallHeap = new int[5];
//小顶堆数据大小
private int smallHeapSize;
//添加数据,暂不考虑扩容,固定数组大小。添加数据不会超标.
public void add(int value) {
data[size++] = value;
//偶数情况下,大顶堆n/2,小顶堆n/2,奇数情况下,大顶堆n/2+1,小顶堆n/2.且大顶堆的数据比小顶堆多
if (size % 2 == 0) {
//大顶堆堆顶元素大于该元素,将大顶堆元素删除。放入小顶堆。该元素加入大顶堆。
int temp = value;
if (bigHeap[0] > value) {
temp = bigHeap[0];
bigHeap[0] = value;
bigHeapAdjust(bigHeap, 0, bigHeapSize);
}
smallHeap[smallHeapSize++] = temp;
smallHeapAdjust(smallHeap,0, smallHeapSize);
} else {
//和小顶堆堆顶元素大小判断
int temp = value;
if (smallHeapSize != 0 && smallHeap[0] < value) {
temp = smallHeap[0];
smallHeap[0] = value;
smallHeapAdjust(smallHeap, 0, smallHeapSize);
}
bigHeap[bigHeapSize++] = temp;
bigHeapAdjust(bigHeap,0, bigHeapSize);
}
}
public int medianNum() {
return bigHeap[0];
}
public static void smallHeapAdjust(int[] data, int index, int length) {
int temp = data[0];
for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {
if (i + 1 < length && data[i] > data[i + 1]) {
//左孩子节点大于右孩子节点,指向右孩子
i++;
}
//如果该结点比最小的孩子节点小,退出
if (temp < data[i]) {
break;
}
//将最小的孩子结点的值赋值给该结点
data[index] = data[i];
index = i;
}
data[index] = temp;
}
public static void bigHeapAdjust(int[] data, int index, int length) {
//从该结点的左子结点开始,也就是2i+1处开始
int temp = data[index];
for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {
if (i + 1 < length && data[i] < data[i + 1]) {
//左孩子节点小于右孩子节点,指向右孩子
i++;
}
//如果该结点比最大的孩子节点大,退出
if (temp >= data[i]) {
break;
}
//将最大的孩子结点的值赋值给该结点
data[index] = data[i];
index = i;
}
data[index] = temp;
}
网友评论