堆排序
假如给你一无序的数组,经过堆排序获得一组降序的数组
1、首先我们将数组遍历,进行heapInsert,变为一个大根堆,建立堆的过程
方法一:正序遍历+heapInsert O(N*logN)
当需要建堆的数量少的时候,代价低,数量高的时候,代价高
for(int i = 0; i < arr.length;i++){
heapInsert(arr,i);//O(log(2,N))
}
方法二:倒序遍历+heapify O(N)
需要建堆的数量少的时候,代价高,数量多的时候,代价低
给你一个数列你可以把它想象成一个大根堆,然后我们从最后一位开始进行heapify,当然没有子节点的是跳过的,就是从后向前找带有子节点的,然后进行heapify,最终得到的数组就是大根堆
for(int i = arr.length - 1 ; i >=0 ;i--){
heapify(arr,i,arr.length)
}
2、把堆的最大值和堆末尾的值进行交换,然后减少堆的大小后,再去调整堆,一直周而复始,时间复杂度为O(N*logN)
3、堆的大小减为0之后,排序完成
//O(N*log(2,N))
public static void heapSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
//把数组整个改为一个大根堆 O(N)
for(int i = 0; i< arr.length;i++){
heapInsert(arr,i);//O(log(2,N))
}
//这样做速度会更快,和上面那个一样
//在数组中从右往左,每一个位置开始做heapify,周而复始得到大根堆
/*for(int i = arr.length - 1 ; i >=0 ;i--){
heapify(arr,i,arr,length)
}*/
//给heapSize赋值
int heapSize = arr.length;
//第一位的数(最大值)和最后一位数字交换,然后heapSize-1
swap(arr, 0, --heapSize);
//一直进行大根堆化、头节点和最后一个交换,直到heapSize变为0
while(heapSize > 0){
heapify(arr, 0, heapSize);//O(log(2,N))
swap(arr, 0, --heapSize);//O(1)
}
}
扩展:使用JAVA自带的堆 O(N*logK)
几乎有序:如果把数组排好顺序的话,每个元素移动的距离可以不超过K,并且K对于数组来说比较小
那么,已知一个几乎有序的数组,请选择一个合适的排序算法来对这个数据进行排序
解法:O(N*log(2,K)),如果K很小,可以看作O(N)
设K=5
1、准备一个小根堆,遍历前6个数,下标为0-5的前6个数全部加入到小根堆中。下标为6的不可能进入遍历,因为它如果是最小值,来到0下标需要移动6个距离,
2、排完序后,由于每个元素移动的距离不可用超过5,所以小根堆的最小值一定在下标为0的位置,然后我们从数组中去除这个最小值,
public static void soredArrDistanceK(int[] arr, int k){
//java中自带的的容器,小根堆,属性就跟大根堆相反呗
PriorityQueue<Integer> heap = new PriorityQueue<>();
//第一次把0-K个数放进小根堆,如果这个里最后一个元素下标根本不到K,就取这俩之间最小的
for(int index = 0; index <= Math.min(arr.length-1, k); index++){
heap.add(arr[index]);
}
//小根堆中动态的保存K+1个数,这个操作就是新进来数,把原来的数弹出,0-K个数放进小根堆,如果这个里最后一个元素下标根本不到K,就取这俩之间最小
for(int i = 0; index <= Math.min(arr.length-1, k); i++, index++){
heap.add(arr[index]);
arr[i] = heap.poll();
}
//小根堆中动态的保持有k+1个数,加入最后一次小根堆弹完不满k+1个数,下发代码就是把所有剩下的数弹出
while(!heap.isEmpty()){
arr[i++] = heap.poll());//弹出最小值,插入数组
}
}
注意什么时候使用自带的堆结构,什么时候手写堆结构:
1、java中自带的堆容器,只允许我们输入和输出,别的操作,比如我们手写的heapify无法实现,就是说自带的容器就是一个黑盒
2、通常我们需要改变内部结构都需要手写堆
比较器
-
实质就是重载比较运算符,比如说数字比大小要用大于小于等于三个关系,但是如果进行其他类型 的比较,怎么定义大于小于等于
-
比较器可以很好的应用在特殊标准的排序上
-
比较器可以很好的应用在根据特殊标准排序的结构上
-
写代码变得容易,用于范性编程
约定俗成的返回值
int compare(T o1, T o2);
-
参数列表代表,两个同一类型的对象,它俩要进行对比
-
返回值int
-
如果返回 -1(或者是负数),就代表o1在前的情况
-
如果返回 1(或者是正数),就代表o2在前的情况
-
如果返回 0 ,代表o1,o2 不分先后
-
例子:自定义student类,让student根据ID大小排序
public class test{
psvm{
Student s1 = new Student(1,"asd",12);
Student s2 = new Student(11,"qwe",11);
Student[] students = new Student[] {s1, s2};
//在调用排序的时候传入你要进行排序的数组,和比较器
Arrays.sort(students, new IdAscendingComparator());
}
}
public class Student{
private Integer id;
private String name;
private Integer age;
//get set 构造器
}
//根据id升序排列的比较器,继承了比较器接口Comparator
public static class IdAscendingComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2){
return o1.id - o2.id;
}
}
自定义堆与比较器
JAVA自带的堆结构,是不能处理堆内部发生变化的,假如堆内部发生了变化,还需要重新再对堆进行根排序化,但是要排序必须要清楚,堆内的对象是如何比较排序的,这里就需要用比较器
例子:resign(),用户对堆里的数据进行了更改,并且要求重建堆结构
例子:resign(),用户对堆里的数据进行了更改,并且要求重建堆结构
public static class MyHeap<T>{
//之前的堆我们都用的数组,但是这里要保存一类的元素进入堆,数组不能指定泛型索性使用arrayList,这个属性就是指的存放堆中数据的
//*******这个属性和indexMap密不可分,二者同步更新******
private ArrayList<T> heap;
//反向表,用于存放 堆中元素(T) 和 它(T)所在arrayList中的下标(Integer)
//*******这个属性和heap密不可分,二者同步更新******
private HashMap<T, Integer> indexMap;
//heap的大小
private int heapSize;
//比较器属性,用于比较堆内元素是如何进行排序的
private Comparator<? super T> comparator;
//构造器,必须传入一个构造器
public MyHeap(Comparator<? super T> com){
heap = new ArrayList<>();
indexMap = new HashMap<>();
heapSize = 0;
comparator = com;
}
//判断是否为空
public boolean isEmpty(){
return heapSize == 0;
}
//获取长度
public int size(){
return heapSize();
}
//堆中是否收过某个元素,直接从反向表中查看是否有就行了
public boolean contains(T key){
return indexMap.containsKey(key);
}
//向堆中添加元素
public void push(T key){
//向堆中添加元素,这个元素在堆list的末尾index=heapSize
heap.add(value);
//同时堆和反向表绑定行动,向反向表中插入:添加的元素,与此时元素所在的位置,肯定在heap的末尾
indexMap.put(value, heapSize);
//执行heapInsert,在末尾插入元素value,执行根堆化,并且让heap大小+1
heapInsert(heapSize++);
}
//返回堆中最大的元素,并且清除掉最大的元素
public T pop(){
//获取到根上最大的值
T ans = heap.get(0);
//获取最后一位的下标
int end = heapSize - 1;
//把最后一位和根节点互换,删掉根节点的值
swap(0, end);
//反向表中,同步删除最大的值
indexMap.remove(ans);
//执行heapify,重新大根堆化
heapify(0, --heapSize);
return ans;
}
//************将堆内的一元素的值进行更新,并不知道更新后的值是多少,只是让你重新排一下堆
public void resign(T value){
//可以根据反向表,获取到更新后的值的下标
int valueIndex = indexMap.get(value);
//根据这个下标,对堆进行insert或者heapify,因为这两个都有条件,并且只能执行一个
heapInsert(valueIndex);
heapify(valueIndex, heapSize);
}
//带有比较器的heapInsert,判断条件就查看比较器返回值是否小于0
public void heapInsert(int index){
while(comparator.compar(heap.get(index), heap.get(index - 1)/2) < 0){
swap(index, (index - 1) / 2);
index = (index - 1)/2;
}
}
//带有比较器的heapify,判断条件就看比较器返回值
public void heapify(int index, int heapSize){
int left = 2 * index + 1;
while(left < heapSize){
int largest = left + 1 < heapSize
&& comparator.compare(heap[left], heap[left+1]) ?
left : left+1;
largest = comparator.compare(heap[largest], heap[index]) ?
largest : index;
if(lagest == index){
break;
}
swap(index, largest);
index = largest;
int left = 2 * index + 1;
}
}
//新的交换代码
private void swap(int i, int j){
//通过下标获取到heap中对于保存的值
T o1 = heap.get(i);
T o2 = heap.get(j);
//直接调用list中的set方法,通过给i下标赋值j的值,j下标处赋值i的值完成交换
heap.set(i, o2);
heap.set(j, o1);
//同样,我们的反向表也必须进行更改
indexMap.put(o1, j);
indexMap.put(o2, i);
}
}
leetcode 215 数组的第K个最大元素
215、数组中的第K个最大元素
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
for (int j = heapSize -1 ; j >= 0; j--) {
heapify(nums, j, heapSize);
}
for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);
--heapSize;
heapify(nums, 0, heapSize);
}
return nums[0];
}
public void heapify(int[] heap, int index, int heapSize) {
int left = 2 * index + 1;
while(left < heapSize){
int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
largest = heap[largest] > heap[index] ? largest : index;
if(largest == index){
break;
}
swap(heap, index, largest);
index = largest;
left = 2 * index + 1;
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
标签:index,arr,int,堆排序,public,heapSize,heap,比较 From: https://www.cnblogs.com/phonk/p/16602240.html