网站外包合作,广州市海珠区建设局网站,中国十大热门网站,长沙做公司网站1.堆#xff08;Heap#xff09;
1.1堆的概念
堆是一种非常重要的数据结构#xff0c;通常被实现为一种特殊的完全二叉树
如果有一个关键码的集合K{k0,k1,k2,...,kn-1}#xff0c;把它所有的元素按照完全二叉树的顺序存储在一个一维数组中#xff0c;如果满足kik2i…1.堆Heap
1.1堆的概念
堆是一种非常重要的数据结构通常被实现为一种特殊的完全二叉树
如果有一个关键码的集合K{k0,k1,k2,...,kn-1}把它所有的元素按照完全二叉树的顺序存储在一个一维数组中如果满足kik2i1且kik2i2(i0,1,2,3...)则称这个集合为小堆如果满足kik2i1且kik2i2(i0,1,2,3...)则称这个集合为大堆。
简单来说根节点的值为最大的堆叫做最大堆或大根堆根节点的值最小的堆叫做最小堆或小根堆 1.2堆的性质
1.完全二叉树的性质
除了最后一层外每一层都被填满最后一层的节点从左往后填充
2.堆序性质
最大堆大根堆
对于每个节点i其左子节点2i1和右子节点2i2的值都小于或等于i的值
最小堆小根堆
对于每个节点i其左子节点2i1和右子节点2i2的值都大于或等于i的值 1.3堆的存储方式
从堆的概念可知堆是一颗完全二叉树因此可以以层序的规则方式来高效存储 注意 对于非完全二叉树来说不适合使用顺序的方式进行存储因为为了还原二叉树空间中必须要存储空节点就会导致空间利用率比较低 1.4堆的创建
给定一个集合{28,16,20,19,29,35,66,50,26,38}如何将其创建为堆呢 观察发现根节点的左右子树都已经满足堆的性质因此只需要将根节点向下调整即可
1.4.1堆的向下调整
1.用parent表示要调整的节点child表示parent的左孩子注意堆是一颗完全二叉树如果parent有孩子一定是先有左孩子
2.如果parent的左孩子存在即childsize进行如下操作直到parent的左孩子不存在 parent的右孩子是否存在如果存在则找到左右孩子中最小的元素让child表示这个元素。 将parent与较小的孩子child进行比较如果parent小于child调整结束。 如果parent大于child将parent和child进行交换原来parent中较大的元素向下调整可能会导 致子树不满足堆的性质因此要继续向下调整即parentchildchild2*parent1继续进 行步骤2 代码编写 public void shiftDown(int[] array,int parent){int child2*parent1;int sizearray.length;while(childsize){//如果右孩子存在用child标记左右孩子中较小的值if(child1sizearray[child1]array[child]){child;}if(array[parent]array[child]){swap(array,parent,child);//继续向下调整为了保证子树也满足堆的性质parentchild;child2*parent1;}else{break;}}}private void swap(int[] array,int a,int b){int tmparray[a];array[a]array[b];array[b]tmp;} 注意再调整以parent为根的二叉树时必须满足parent的左子树和右子树已经时堆了才可以进行向下调整。 1.4.2堆的创建小根堆
那么对于普通的序列即根节点的左右子树不满足堆的性质又该如何创建呢
例如对普通序列{2,7,8,5,4,1}进行小根堆的创建
根据上面的堆的向下调整我们的思路就是要将根的左右子树都满足小根堆的特点我们可以从下向上从最后一个非叶子节点出发将其与他们的左右孩子进行比较将最小的值与非叶子节点进行交换堆的向下调整再继续向上执行上述操作直到操作的节点为根节点即可 代码编写 public void createSmallestHeap(int [] array){int root(array.length-2)1;for(;root0;root--){shiftDown(array,root);}} 1.5堆的插入和删除
1.5.1堆的插入
堆的插入总共需要2步
1.先将元素放入底层空间不够时需要进行扩容
2.将新插入的元素不断向上调整直到满足堆的性质 观察可以发现如果新插入的节点的父节点大于新插入的节点就进行元素的交换不断重复该动作
代码编写 //child表示新插入元素的索引public void shiftUp(int child){//找到新插入节点的父节点int parent(child-1)/2;while(child0){if(array[parent]array[child]){swap(array,parent,child);childparent;parent(child-1)/2;}else {break;}}}
1.5.2堆的删除
堆在删除过程中需要注意删除的元素一定是堆顶元素
1.将堆顶元素和堆中的左后一个元素交换位置
2.将堆中有效个数减少一个
3.对堆顶元素进行向下调整 代码编写 public void shiftDown(int[] array,int parent){int child2*parent1;int sizearray.length;while(childsize){//如果右孩子存在用child标记左右孩子中较小的值if(child1sizearray[child1]array[child]){child;}if(array[parent]array[child]){swap(array,parent,child);//继续向下调整为了保证子树也满足堆的性质parentchild;child2*parent1;}else{break;}}}public void delete(int[] array){swap(array,0,size-1);//size表示有效元素的个数size--;shiftDown(array,0);} 1.6堆的应用
1.堆排序Heap Sort
利用堆的性质对数组进行排序时间复杂度为O(nlogn)
2.优先级队列PriorityQueue
堆是实现优先级队列的高校数据结构支持快速的插入和删除操作
3.Dijkstra算法
在最短路径算法中堆用于高效地选择当前距离最小的节点
4.Kth Largest Element
也叫topK问题使用堆可以高效地找到数组中的第k大元素 2.PriorityQueue
2.1什么是优先级队列
通过之前的介绍队列是一种先进先出(FIFO)的数据结构但是优先情况下操作的数据可能带有优先级并不希望按照队列原始的顺序进行出栈可能优先级高的元素想先出队列
在生活中有一个很常见的例子当你在用听歌的时候突然接到电话音乐会自动停止而执行通话的操作
优先级队列PriorityQueue是一种特殊的队列其中的每个元素都有一个优先级队列会根据优先级来决定元素的出队顺序优先级高的元素先出队优先级低的元素后出队如果两个元素的优先级相同则按照它们入队列的顺序出队
优先级队列通常基于堆这种数据结构实现因为堆可以高效地进行插入和删除操作同时保持元素的优先级顺序
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的我们主要进行讲解PriorityQueue 2.2PriorityQueue常见操作
PriorityQueue的常见方法
方法解释PriorityQueue()创建一个空的优先级队列默认容量是11PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列注意initialCapacity不能小于1否则会抛出IllegalArgumentException异常PriorityQueue(Collection? extends E c)用一个集合来创建优先级队列boolean offer(E e)插入元素e插入成功返回true如果e对象为空则会抛出NullPointerException异常空间不够的时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll()移除优先级最高的元素如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空队列boolean isEmpty()检测优先级队列是否为空如果为空返回true 我们以一个复杂的类型来演示
public class Student implements ComparableStudent{private String name;private int age;public Student() {}public Student(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return Student{ name name \ , age age };}Overridepublic int compareTo(Student o) {return this.age-o.age;}
}public class Test {public static void main(String[] args) {PriorityQueueStudent queuenew PriorityQueue();Student s1new Student(hajimi,21);Student s2new Student(king,18);queue.offer(s1);queue.offer(s2);System.out.println(queue.size());for(Student s:queue){System.out.println(s);}queue.clear();System.out.println(queue.size());}
} 2.3优先级队列的特性
因为优先级队列是基于堆实现的所以优先级队列的操作的时间复杂度其实就是堆在操作过程中的时间复杂度
1.插入
将一个新元素插入到队列中并根据优先级调整队列的顺序时间复杂度为O(logn)
2.删除
删除优先级最高的元素时间复杂度为O(logn)
3.获取优先级最高的元素
返回优先级最高的元素但不删除它时间复杂度为O(1)
4.更新优先级
更新队列中某个元素的优先级并调整队列的顺序时间复杂度为O(logn)
5.Priority中放置的元素必须是能够比较大小的不能插入无法比较大小的对象否则会抛出ClassCastException异常
6.不能插入null否则会抛出NullPointerException
7.PriorityQueue默认情况下是小堆
8.PriorityQueue其内部可以自动扩容 2.4PriorityQueue底层的扩容原理 PriorityQueue的 默认无参构造方法创建的数组长度为11 如果容量小于64时是按照oldCapacity的2倍方式扩容的
如果容量大于64时是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容 2.5实现一个优先级队列
package datastructure;import java.util.Arrays;public class PriorityQueue {private int elem[];//队列中有效元素的个数private int usedSize;private final static int DEFAULT_INIT_SIZE11;public PriorityQueue(){elemnew int[DEFAULT_INIT_SIZE];}public PriorityQueue(int[] elem){this.elemelem;this.usedSizeelem.length;int root((elem.length-2)1);for(;root0;root--){shiftDown(root,elem.length);}}private void shiftDown(int parent,int len){int childparent*21;while (childlen){if(child1lenelem[child1]elem[child]){child;}if(elem[parent]elem[child]){swap(elem,parent,child);}else {break;}}}public boolean offer(int value){if(usedSizeelem.length){Arrays.copyOf(elem,2*elem.length);}elem[usedSize]value;usedSize;shiftUp(usedSize-1);return true;}private void swap(int[] elem,int a,int b){int tmpelem[a];elem[a]elem[b];elem[b]tmp;}private void shiftUp(int child){int parent(child-1)/2;while (child0){if(elem[child]elem[parent]){swap(elem,parent,child);childparent;parent(child-1)/2;}else {break;}}}public int size(){return usedSize;}public int peek(){if(usedSize0){System.out.println(优先级队列中没有元素无法获取元素);return -1;}return elem[0];}public boolean isEmpty(){return usedSize0;}public int poll(){if(usedSize0){System.out.println(优先级队列中没有元素无法删除元素);return -1;}int valueelem[0];swap(elem,0,usedSize-1);usedSize--;shiftDown(0,usedSize-1);return value;}
}对编写的代码进行运行测试
public class Test {public static void main(String[] args) {PriorityQueue queuenew PriorityQueue();queue.offer(2);queue.offer(4);queue.offer(3);queue.offer(8);queue.offer(7);queue.offer(5);queue.offer(1);System.out.println(queue.peek());int a queue.poll();System.out.println(a);System.out.println(queue.peek());System.out.println(queue.size());}
}
