网站建设攻略,wordpress修改注册页面,建设营销型网站广州,邢台建设一个企业网站目录
优先级队列
堆的概念
堆的创建
堆的向下调整
堆的插入
完整代码 优先级队列
队列是一种先进先出的数据结构#xff0c;有些时候操作的数据可能带有优先级#xff0c;出队列时就需要优先级高的数据先出队列。
在这种情况下#xff0c;数据结构应该提供两个最基本…目录
优先级队列
堆的概念
堆的创建
堆的向下调整
堆的插入
完整代码 优先级队列
队列是一种先进先出的数据结构有些时候操作的数据可能带有优先级出队列时就需要优先级高的数据先出队列。
在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。
堆的概念
如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足Ki K2i1 且 Ki K2i2) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 注意 已知孩子节点为i则双亲节点为 (i-1)/2已知双亲节点为i左孩子2*i1右孩子2*i2。 堆的创建
堆的向下调整
这里以大根堆为例来讲解堆的向下调整。 题目对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据如果将其创建成大根堆呢 首先我们要定义基本变量来供使用。因为是对于集合中的数据进行创建大根堆所以我们可以使用数组来进行。
public class TestHeap {public int[] elem;public int usedSize;public TestHeap(){this.elem new int[10];}
}
对于如何把数组中的数据放到实现堆的数组里我们可以通过for循环来进行放置。
注意这里是有两个数组。 public void intelem(int[] array){for (int i 0; i array.length; i) {this.elem[i] array[i];usedSize;}}
接着我们就要开始创建堆了 public void createHeap(){for (int parent (this.usedSize-1-1)/2; parent 0 ; parent--) {shifDown(parent, this.usedSize);//每棵树结束时候都给个10如果接着调整的节点比10//大了说明这棵树一定调整完了}}
主要的重心在于如何写出shifDown这个方法。 思路
由上面我们能知道 child parent*21。为了确保child的数组不越界我们要确定循环条件。因为是创建大根堆所以要找到左右子树的最大值同根节点进行比较、交换。关于break这里因为当 前一个节点已经结束了下面的节点也是结束的状态。 /**** param parent 每棵子树调整的起始位置* param usedSize 判断 每棵子树 什么时候 调整结束*/private void shifDown(int parent, int usedSize) {int child 2*parent1;while(child usedSize){//找到左右子树的最大值if(child1 usedSize elem[child] elem[child1]){child;}if(elem[child] elem[parent]){swap(elem,child,parent);parent child;child 2*parent1;}else{break;}}}private void swap(int[] elem, int i ,int j){int tmp elem[i];elem[i] elem[j];elem[j] tmp;}
通过Test测试类和调试我们能看到大根堆创建成功了。
public class Test {public static void main(String[] args) {int[] array {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap new TestHeap();//把array的值赋值给testHeaptestHeap.intelem(array);testHeap.createHeap();
} 创建的堆下图大根堆。 堆的插入 堆的插入总共需要两个步骤 先将元素放入到底层空间中(注意空间不够时需要扩容)将最后新插入的节点向上调整直到满足堆的性质 其实这和上面的创建大根堆有些类似但这里用到的是向上调整。 //插入public void push(int val){if(isFull()){elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize] val;sitUp(usedSize);usedSize;}public boolean isFull(){return elem.length usedSize;}
}这里的关键在于向上调整部分代码的编写。 private void sitUp(int child) {int parent (child-1)/2;while(parent 0){if (elem[parent] elem[child]){swap(elem,child,parent);child parent;parent (child-1)/2;}else{break;}}}
向上调整我们可以先确定孩子节点最后一棵树的节点位置可以通过 useSize来确定进而能确定双亲节点。
完整代码
TestHeap类
import java.util.Arrays;public class TestHeap {public int[] elem;public int usedSize;public TestHeap(){this.elem new int[10];}public void intelem(int[] array){for (int i 0; i array.length; i) {this.elem[i] array[i];usedSize;}}public void createHeap(){for (int parent (this.usedSize-1-1)/2; parent 0 ; parent--) {shifDown(parent, this.usedSize);//没棵树结束时候都给个10如果接着调整的节点比10大了。说明这棵树一定调整完了}}//altpenter 直接生成/**** param parent 每棵子树调整的起始位置* param usedSize 判断 每棵子树 什么时候 调整结束*/private void shifDown(int parent, int usedSize) {int child 2*parent1;while(child usedSize){//找到左右子树的最大值if(child1 usedSize elem[child] elem[child1]){child;}if(elem[child] elem[parent]){swap(elem,child,parent);parent child;child 2*parent1;}else{break;}}}//插入public void push(int val){if(isFull()){elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize] val;sitUp(usedSize);usedSize;}private void swap(int[] elem, int i ,int j){int tmp elem[i];elem[i] elem[j];elem[j] tmp;}private void sitUp(int child) {int parent (child-1)/2;while(parent 0){if (elem[parent] elem[child]){swap(elem,child,parent);child parent;parent (child-1)/2;}else{break;}}}public boolean isFull(){return elem.length usedSize;}
}
Test类
public class Test {public static void main(String[] args) {int[] array {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap new TestHeap();//把array的值赋值给testHeaptestHeap.intelem(array);testHeap.createHeap();/*for (int i 0; i array.length; i) {testHeap.push(array[i]);}testHeap.push(80);*/}
}
