1.shiftup 对于数组新插入节点,变换后让其成为最大或者最小堆。
2.shiftdown
让一个节点下移以至于满足最大或者最小堆。
3.heapify
heapify(): 这里是指最大heapify。 我们只需要从 k = N / 2开始, 在k >= 1的条件下对 k 进行shiftDown(), 然后k--就可以了。从最后一个不是叶子的节点开始,执行shiftDown()操作。
public void heapSort(int [] arr){
if (arr == null || arr.length < 2) {
return;
}
// for (int i = 0; i < arr.length; i++) {
// shiftUp(arr, i);
// }
heapify(arr.length,arr);
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
shiftDown(arr, 0, size);
swap(arr, 0, --size);
}
}
private static void shiftUp(int [] array, int index){
while (array[(index-1)/2] < array[index]){
swap(array,index,(index-1)/2);
index = (index-1)/2;
}
}
public void shiftDown(int [] array,int index,int size){
int left = 2*index+1;
while (left<size){
int largest = left+1<size && array[left+1]>array[left] ? left+1 : left;
largest = array[largest] > array[index] ? largest:index;
if (largest == index){
break;
}
swap(array,largest,index);
index = largest;
left = index * 2 +1;
}
}
public static void heapify(int size,int[] array){
for (int i = (size -2)/2 ; i>=0;i--){
shiftDown(array,i,size);
}
}
另一种写法:
private void siftdown(int[] A, int k) {
while (k * 2 + 1 < A.length) {
int son = k * 2 + 1;
if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])
son = k * 2 + 2;
if (A[son] >= A[k])
break;
int temp = A[son];
A[son] = A[k];
A[k] = temp;
k = son;
}
}
public void heapify(int[] A) {
for (int i = (A.length - 1) / 2; i >= 0; i--) {
siftdown(A, i);
}
}
有一个数据流,依次出来一个数据,如何能够实时的取出中位数。
思路:采用一个最小堆和一个最大堆
最小堆存放较大的N/2个数据
最大堆存放较小的N/2个数据
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。