沧州国外网站建设,手机触屏网站开发教程,网站底部的制作,wordpress做社交网站堆排序#xff08;二#xff09;
把数组从零开始连续的一段 完全二叉树 size
i 左 son 2*11
i 右 son 2*12
父 (i-1) / 2
堆是完全二叉树#xff0c;分为大根堆和小根堆
在完全二叉树里#xff0c;每一棵子数最大的值是头节点的值#xff0c;就是大根堆
同理…堆排序二
把数组从零开始连续的一段 完全二叉树 size
i 左 son 2*11
i 右 son 2*12
父 (i-1) / 2
堆是完全二叉树分为大根堆和小根堆
在完全二叉树里每一棵子数最大的值是头节点的值就是大根堆
同理在完全二叉树里每一棵子数最小的值是头节点的值就是小根堆
大根堆排序插入的值 和 父节点比较如果比父节点大和它交换直到最大就停止通过这样的调整得到的一定是大根堆。这个过程我们叫做 heapInsert
public static void heapInsert(int [] arr, int index) {while (arr[index] arr[(index - 1) / 2]) {// 和父节点交换值 并且把当前下标移动到父节点swap(arr, index, (index - 1) / 2); index (index - 1) / 2; }
}从一堆数中找出最大值移除它保持还是大根堆我们管这个过程叫做heapify
public static void heapify(int [] arr, int index, int heapSize) {int left index * 2 1; // 左孩子的下标while (left heapSize) { // 下方还有孩子 (左孩子越界那么就没有右孩子了。)// 俩个孩子中谁的值大把下标给谁 先找出孩子中最大的int largest left 1 heapSize arr[left 1] arr[left] ? left 1:left;// 父和孩子之间谁的值大把下标给谁 较大的孩子和父节点找出最大的largest arr[largest] arr[index] ? largest : index;if (largest index) { // 如果当前节点就是最大的 跳出break;}swap(arr, largest, index); // 交换位置index largest; // 继续比较left index * 2 1; // 找左孩子继续 while}
}题目
已知一个几乎有序的数组几乎有序是指如果把数组排好顺序的话每个元素移动的距离可以不超过K并且K相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
假如K 6 建立一个heapSize 7 的小根堆 这样小根堆的最小值一定是数组的最小值
把最小的弹出保持小根堆新加入的数字做heapfiy
继续上面的步骤直到全部弹出。
public static void main(String[] args) {PriorityQueueInteger heap new PriorityQueue();heap.add(8);heap.add(4);heap.add(10);heap.add(3);while(!heap.isEmpty) {System.out.println(heap.poll());}
}
