景德镇网站建设,营销软文范例大全300字,wordpress 子分类,动漫制作专业有本科吗目录 1. 优先级队列的概念 1.1堆的概念 1.2堆的性质 1.3堆的存储方式 2. 堆的创建 2.1堆的创建代码解析 2.2建堆的时间复杂度 2.3堆的插入 2.4 堆的删除 2.5常见习题 1. 优先级队列的概念 队列是一种先进先出 (FIFO) 的数据结构 #xff0c;但有些情况下#xff0c; 操作的数… 目录 1. 优先级队列的概念 1.1堆的概念 1.2堆的性质 1.3堆的存储方式 2. 堆的创建 2.1堆的创建代码解析 2.2建堆的时间复杂度 2.3堆的插入 2.4 堆的删除 2.5常见习题 1. 优先级队列的概念 队列是一种先进先出 (FIFO) 的数据结构 但有些情况下 操作的数据可能带有优先级一般出队 列时可能需要优先级高的元素先出队列 在这种情况下 数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象 。这种数 据结构就是 优先级队列 (Priority Queue) 。 1.1堆的概念 如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足Ki K2i1 且 Ki K2i2 (Ki K2i1 且 Ki K2i2) i 012…则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 以大根堆为例 1.2堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 1.3堆的存储方式
从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储 注意 对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节 点就会导致空间利用率比较低 将元素存储到数组中后 假设 i 为节点在数组中的下标则有 如果 i 为 0 则 i 表示的节点为根节点否则 i 节点的双亲节点为 (i - 1)/2 如果 2 * i 1 小于节点个数则节点 i 的左孩子下标为 2 * i 1 否则没有左孩子 如果 2 * i 2 小于节点个数则节点 i 的右孩子下标为 2 * i 2 否则没有右孩子 2. 堆的创建
public class TextHeap {public int[] arr;public int size;public TextHeap(int[] arr) {this.arr arr;sizearr.length;}public void createheap(){for (int parent (size-1-1)/2; parent 0 ; parent--) {shiftDown(parent,size);}}private void shiftDown(int parent,int len){int child2*parent1;while(childlen){if(child1lenarr[child1]arr[child]){child;}if(arr[parent]arr[child]){int tmparr[parent];arr[parent]arr[child];arr[child]tmp;parentchild;child2*parent1;}else {break;}}}
}
2.1堆的创建代码解析
向下过程(以大根堆为例) 让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)如果parent的左孩子存在即:child size 进行以下操作直到parent的左孩子不存在 parent右孩子是否存在存在找到左右孩子中最大的孩子让child进行标将parent与较大的孩子child比较。 如果parent大于较大的孩子child调整结束。 否则交换parent与较大的孩子child交换完成之后parent中大的元素向下移动可能导致子树不满足对的性质因此需要继续向下调整即parent childchild parent*21; 然后继续2。 2.2建堆的时间复杂度 2.3堆的插入 堆的插入总共需要两个步骤 1. 先将元素放入到底层空间中 ( 注意空间不够时需要扩容 )。 2. 将最后新插入的节点向上调整直到满足堆的性质。 代码 public void shiftUp(int child){int parent(child-1)/2;while(child0){if(arr[child]arr[parent]){int tmp arr[parent];arr[parent] arr[child];arr[child] tmp;childparent;parent(child-1)/2;}else {break;}}}public void offer(int val) {if (isfull()) {arr Arrays.copyOf(arr, arr.length * 2);}arr[size] val;}public boolean isfull() {return arr.length size;} 从0开始插入建堆的时间复杂度 2.4 堆的删除 注意堆的删除一定删除的是堆顶元素。 具体如下 1. 将堆顶元素对堆中最后一个元素交换 2. 将堆中有效数据个数减少一个 3. 对堆顶元素进行向下调整 代码 public boolean empty() {return 0 size;}public void pop(){if (empty()){return;}int tmp arr[0];arr[0] arr[size-1];arr[size-1] tmp;size--;shiftDown(0,size);} 2.5常见习题 1. 下列关键字序列为堆的是 :() A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60 D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,32 解析 答案A B为啥错如下其他同理。 2. 已知小根堆为 8,15,10,21,34,16,12 删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 () A: 1 B: 2 C: 3 D: 4 解析 答案C 3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是() A: [3 2 5 7 4 6 8] B: [2 3 5 7 4 6 8] C: [2 3 4 5 7 8 6] D: [2 3 4 5 6 7 8] 解析 答案C 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
