赞
踩
从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储.
我们采用数组的方式实现一课完全二叉树,下述就是基本描述代码.
public class TestHeap { public int[] elem; public int usedSize; public TestHeap() { this.elem = new int[10]; } public void initElem(int[] array) { for (int i = 0; i < array.length; i++) { elem[i] = array[i]; usedSize++; } } }
当然,在我们构建了完全插树之后,我们要进行一系列的操作,接下来的第一个操作就是建堆操作.
我这里给出一个建堆操作的过程,我们以建立最大堆为例子.
以下方法的思路如下:
大家可以参考一下.
shiftDown 方法的思路如下:
createHeap 方法的思路:
public void createHeap() { for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) { shiftDown(parent,usedSize); } } /** * 父亲下标 * 每 * 棵树的结束下标 * @param parent * @param len */ private void shiftDown(int parent,int len) { int child = 2*parent + 1; //最起码 要有左孩子 while (child < len)( { //一定是有右孩子的情况下 if(child+1 < len && elem[child] < elem[child+1]) { child++; } //child下标 一定是左右孩子 最大值的下标 if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2*parent+1; }else { break; } } }
下面是时间复杂度的分析过程.
数据的插入
向上调整的具体过程
下面的代码思路如下:
shiftUp 方法的思路如下:
offer 方法的思路:
//向上调整建堆的时间复杂度:N*logN public void offer(int val) { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val;//11 //向上调整 shiftUp(usedSize-1);//10 } private void shiftUp(int child) { int parent = (child-1)/2; while (child > 0) { if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child-1)/2; }else { break; } } }
具体的向上调整时间复杂度分析
删除过程如下:
具体思路如下:
pop 方法的思路:
public void pop() { if(isEmpty()) { return; } swap(elem,0,usedSize-1); usedSize--; shiftDown(0,usedSize); } private void shiftDown(int parent,int len) { int child = 2*parent + 1; //最起码 要有左孩子 while (child < len) { //一定是有右孩子的情况下 if(child+1 < len && elem[child] < elem[child+1]) { child++; } //child下标 一定是左右孩子 最大值的下标 if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2*parent+1; }else { break; } } }
再开始堆的拓展之前,我们先来看一个概念,就是java里面优先队列api的概念
概念
队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列
数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,这里主要是介绍的是PriorityQueue.
PriorityQueue的构造方法解释
第一种
构造方法没有比较器,直接传入参数.
第二种
指定初始化容量
第三种
这一种就是指定比较器,也是我们实现最大堆的关键因素.
看了上面的构造方法,我们,我们发现这个优先队列是可以指定比较器的,这样我们就可以实现堆的大小,可以定义大根堆,还可以定义小根堆.
具体先来看看,为什么一开始,我们说优先队列构建的是小根堆.
看代码构建.
接下来我会一一解释这些方法,你尽量代入我们上面实现的思想,你就能一下子明白了.
grow方法的解释
siftUpComparable和siftUpUsingComparator
整个offer的逻辑:
看了上面的例子之后,我们发现在我们没有指定具体的比较器或者说实现compareto接口的时候,他调用自己的比较器,进行比较,所以默认是小根堆,这里我们可以利用比较器的知识,
我用下面的例子来说明一下,怎么构建大根堆,代码如下:
class Student implements Comparable<Student>{ public int age; public String name; public Student(String name,int age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } @Override public int hashCode() { return Objects.hash(age, name); } @Override public int compareTo(Student o) { return this.age - o.age; //return o.age - this.age;//大根堆了 } } public class Test { public static void main(String[] args) { Queue<Student> priorityQueue2 = new PriorityQueue<>(); priorityQueue2.offer(new Student("zhangsan",27)); priorityQueue2.offer(new Student("lisi",15)); System.out.println(2111); } }
当然我们还有另外一种方式,就是传入比较器
class Student{ public int age; public String name; public Student(String name,int age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } @Override public int hashCode() { return Objects.hash(age, name); } class AgeComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o2.age-o1.age; } } } public static void main(String[] args) { AgeComparator ageComparator = new AgeComparator(); Queue<Student> priorityQueue2 = new PriorityQueue<>(ageComparator); priorityQueue2.offer(new Student("zhangsan",27)); priorityQueue2.offer(new Student("lisi",15));
具体图示如下:
使用的注意事项
1.使用时必须导入PriorityQueue所在的包,即:
2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出
ClassCastException异常
3. 不能插入null对象,否则会抛出NullPointerException
4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
我这里以最大的k个元素为例子
第一种思路:
通过维持一个大小为N的最小堆,并从中弹出K个元素,从而找到数组中最大的K个元素。
代码如下:
public int[] smallestK(int[] arr, int k) { int[] ret = new int[k]; if(arr == null || k == 0) { return ret; } //O(N*logN) Queue<Integer> minHeap = new PriorityQueue<>(arr.length); for (int x: arr) { minHeap.offer(x); } //K * LOGN for (int i = 0; i < k; i++) { ret[i] = minHeap.poll(); } return ret; }
第二种思路:
具体过程
代码如下:
/** * 前K个最大的元素 * N*logK */ public static int[] maxK(int[] arr, int k) { int[] ret = new int[k]; if(arr == null || k == 0) { return ret; } Queue<Integer> minHeap = new PriorityQueue<>(k); //1、遍历数组的前K个 放到堆当中 K * logK for (int i = 0; i < k; i++) { minHeap.offer(arr[i]); } //2、遍历剩下的K-1个,每次和堆顶元素进行比较 // 堆顶元素 小的时候,就出堆。 (N-K) * Logk for (int i = k; i < arr.length; i++) { int val = minHeap.peek(); if(val < arr[i]) { minHeap.poll(); minHeap.offer(arr[i]); } } for (int i = 0; i < k; i++) { ret[i] = minHeap.poll(); } return ret; }
具体步骤
分为两步:
private void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * 时间复杂度:n*logn * 空间复杂度:O(1) */ public void heapSort() { int end = usedSize-1;//9 while (end > 0) { swap(elem,0,end); shiftDown(0,end); end--; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。