轻松堆的使用
堆的概念
-
堆是一颗顺序存储的二叉树,激素hi将二叉树层序遍历放到数组当中,是完全二叉树。
-
已知双亲(parent)的下标,则:
左孩子(left)下标 = 2 * parent 1。
右孩子(right)下标 = 2 * parent 2。 -
已知孩子(不区分左右)(child)下标,则:
双亲(parent)下标 = (child - 1) / 2。 -
堆有大根堆和小根堆两种:
大根堆:每个根都比结点大。
小根堆:每个根都比结点小。 -
堆对应的集合:priorityQueue(优先级队列)是完全二叉树。
-
堆物理上是保存在数组当中
实现堆
因为堆在物理上是数组,所以通过数组来实现。
定义参数
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
向下调整
把数据从上往下调整,然后形成堆。但前提是:左右子树必须已经是一个堆,才可以调整。一般在插入元素的时候进行向下调整。
说明
- array 代表存储堆的数组
- size 代表数组中被视为堆数据的个数
- index 代表要调整位置的下标
- left 代表 index 左孩子下标
- right 代表 index 右孩子下标
- min 代表 index 的最小值孩子的下标
过程
- index 如果已经是叶子结点,则整个调整过程结束:
判断 index 位置有没有孩子
因为堆是完全二叉树,没有左孩子就一定没有右孩子,所以判断是否有左孩子
因为堆的存储结构是数组,所以判断是否有左孩子即判断左孩子下标是否越界,即 left >= size 越界 - 确定 left 或 right,谁是 index 的最小孩子 min
如果右孩子不存在,则 min = left
否则,比较 array[left] 和 array[right] 值得大小,选择小的为 min - 比较 array[index] 的值 和 array[min] 的值,如果 array[index] <= array[min],则满足堆的性质,调整结束
- 否则,交换 array[index] 和 array[min] 的值
- 然后因为 min 位置的堆的性质可能被破坏,所以把 min 视作 index,向下重复以上过程
如图
像这样通过向下调整,就得到了一个小根堆。
调整前:int[] array = { 27,15,19,18,28,34,65,49,25,37 };
调整后:int[] array = { 15,18,19,25,28,34,65,49,27,37 };
所以代码如下:
public void shiftDown(int parent, int len) {
int child = 2*parent 1;
while (child < len) {
if (child 1 < len && elem[child] < elem[child 1]) {
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;
}
}
}
创建堆
因为向下调整是适用于插入一个数据之后依然是堆,所以我们可以从第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。代码如下:
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i ) {
elem[i] = array[i];
this.usedSize ;
}
for ( int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
//调整
shiftDown(parent, usedSize);
}
}
向上调整
向上调整用在入堆的时候。当一个元素入堆之后,其实是放在二叉树的最后面的。如图:
把新入堆的元素调整之后,保证还是一个大根堆或者小根堆。代码如下:
private void shiftUp(int child) {
int parent = (child - 1)/2;
while (parent >= 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;
}
}
}
判断是否满
判断是否满的时候,只需将 usedSize 和数组长度比较就可以了。代码如下:
public boolean isFull() {
return usedSize == elem.length;
}
插入堆
向上调整是为了方便一个元素插入堆中,所以插入的时候,只需判断是否满了,如果没满,就向上调整。代码如下:
public void offer(int val) {
if (isFull()) {
//满了 扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize ] = val;
//传入的是 usedSize - 1
shiftUp(usedSize-1);
}
判断堆是否为空
判空的方法就是看 usedSize 是否为 0 即可。
public boolean isEmpty() {
return usedSize == 0;
}
出堆顶元素
先判断堆是否为空,然后拿到堆顶元素,然后把堆顶元素的值改为堆的最后一个元素,然后向下调整就好了。代码如下:
public int poll() {
if (isEmpty()) {
throw new RuntimeException("优先级队列为空!");
}
int tmp = elem[0];
elem[0] = elem[usedSize - 1];
elem[usedSize - 1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
拿到堆顶元素
先判断堆是否为空,然后返回数组 0 下标的元素就可以了。代码如下:
public int peek() {
if (isEmpty()) {
throw new RuntimeException("优先级队列为空!");
}
return elem[0];
}
堆排序
这里的排序就是每次都进行向下调整,直到全部调整完成。代码如下:
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
代码测试
public static void main(String[] args) {
int[] arr = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
testHeap.createHeap(arr);
//得到调整之后的结果
System.out.println(Arrays.toString(testHeap.elem));
testHeap.offer(80);
//每次入队之后还是大根堆
System.out.println(Arrays.toString(testHeap.elem));
//每次出队 也要保证大根堆和小根堆 先交换 0 下标和最后下标的位置,然后向下调整就可以了
System.out.println(testHeap.poll());
//每次弹出的都是最大的元素
System.out.println(Arrays.toString(testHeap.elem));
}
运行结果如下:
测试堆排序
public static void main(String[] args) {
int[] arr = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
testHeap.createHeap(arr);
testHeap.heapSort();
System.out.println(Arrays.toString(testHeap.elem));
}
运行结果如下:
优先级队列
优先级队列是 : PriorityQueue 。这里默认就是一个小根堆,每次放入之后还是小根堆。弹出之后还是小根堆。代码如下:
public static void main2(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(12);
priorityQueue.offer(3);
priorityQueue.offer(15);
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
}
运行结果如下:
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggfhic
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13