网站加seo需要多少钱,手机网站开发要多久,怎样建一个免费网站,徐州seo外包平台一、二叉树的顺序存储
在前面我们已经讲了二叉树的链式存储#xff0c;就是一棵树的左孩子和右孩子 而现在讲的是#xff1a;顺序存储一棵二叉树。
1.1、存储方式 使用数组保存二叉树结构#xff0c;方式即将二叉树用层序遍历方式放入数组中。 一般只适合表示完全二叉树就是一棵树的左孩子和右孩子 而现在讲的是顺序存储一棵二叉树。
1.1、存储方式 使用数组保存二叉树结构方式即将二叉树用层序遍历方式放入数组中。 一般只适合表示完全二叉树因为非完全二叉树会有空间的浪费。 这种方式的主要用法就是堆的表示 下标关系
已知双亲(parent)的下标则 左孩子(left)下标 2 * parent 1; 右孩子(right)下标 2 * parent 2;
已知孩子不区分左右(child)下标则 双亲(parent)下标 (child - 1) / 2;
也就是前面我们将的性质5 对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有 1若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点 2若2i1n左孩子序号2i1否则无左孩子 3若2i2n右孩子序号2i2否则无右孩子 二、堆
2.1、概念 堆逻辑上是一棵完全二叉树堆物理上是保存在数组中满足任意结点的值都大于其子树中结点的值叫做大堆或者大根堆或者最大堆反之则是小堆或者小根堆或者最小堆堆的基本作用是快速找集合中的最值 无论是 大根堆还是小根堆 它们的 最值【最大值 和 最小值】都处于 二叉树的 根结点处。要想获得 最值直接 peek 方法就能获得 树 的 根结点值 / 最值。 2.2、操作-向下调整
前提左右子树必须已经是一个 堆 / 逻辑上是一棵完全二叉树。 将一组 记录完全二叉树数据 的 数组 转换成 大根堆。
向下调整出现的问题 得出结论:其实每棵树的调整结束位置都是一样的︰不能超过数组长度。 如何构造一个 向下调整的函数 - 重点
public class TestHeap {public int[] elem;//底层是一个数组public int usedSize;//public TestHeap(){this.elem new int[10];}/*** 创建堆* param array 堆里面存放的元素*/public void creatHeap(int[] array){//将array数组的元素存入elme 数组for (int i 0; i array.length; i) {elem[i] array[i] ;usedSize;}for (int praent (usedSize-1-1)/2; praent 0; praent--) {shiftDown(praent,usedSize);}}/*** 向下调整* param praent 每棵子树的父亲节点* param len 调整的结束位置不能大于数组的长度*/public void shiftDown(int praent, int len){int child 2praent 1;while (child len){if(child 1 len this.elem[child] this.elem[child1]){child;}if(elem[child] elem[praent]){int tmp elem[child];elem[child] elem[praent];elem[praent] tmp;}else {break;}}}
}测试一下
模拟实现 堆 的 时间复杂度 上图转载于堆 / 优先队列
粗略估算可以认为是在循环中执行向下调整为 O(n * log(n)) 了解实际上是 O(n) 堆排序中建堆过程时间复杂度O(n)怎么来的
2.3、操作-建堆
下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆
图示以大堆为例
// 建堆前
int[] array { 1,5,3,8,7,6 };
// 建堆后
int[] array { 8,7,6,5,1,3 };三、堆的应用-优先级队列
3.1、概念 在很多应用中我们通常需要按照优先级情况对待处理对象进行处理比如首先处理优先级最高的对象然后处理次 高的对象。最简单的一个例子就是在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话。 在这种情况下我们的数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这 种数据结构就是优先级队列(Priority Queue) 优先级队列的实现方式有很多但最常见的是使用堆来构建
3.2、堆的基本操作
我们知道堆分为大根堆和小根堆那Java中自带的默认是大根堆还是小根堆 Java集合中默认是小根堆
我们测试一下
public static void main(String[] args) {PriorityQueueInteger priorityQueue new PriorityQueue();priorityQueue.offer(12);priorityQueue.offer(3);priorityQueue.offer(18);System.out.println(priorityQueue.poll());System.out.println(priorityQueue.poll());}优先级队列 - 模拟实现入队 – offer
/*** 插入元素* param val*/public void offer(int val){if(isFull()){//扩容elem Arrays.copyOf(elem,2*elem.length);}//没有满就将val放在数组的最后一个元素elem[usedSize] val;usedSize;//然后就调整堆使其成为一个大根堆shiftUp(usedSize-1,val);}/**** param child 孩子节点的坐标* param val 要插入的值*/public void shiftUp(int child, int val){int praent (child - 1) / 2;while(praent 0){if(elem[child] elem[praent]){int tmp elem[child];elem[child] elem[praent];elem[praent] tmp;//然后再改变child 和 praent 的指向child praent;praent (child - 1) / 2;}else {break;}}}public boolean isFull(){return this.elem.length usedSize;}优先级队列 - 模拟实现出队 – poll
public int poll(){if(isFull()){throw new RuntimeException(队列为null);}//先将0下标和数组的最后一个元素交换int tmp elem[0];elem[0] elem[usedSize-1];elem[usedSize-1] tmp;usedSize--;//然后向下调整0下标这棵树shiftDown(0,usedSize);return tmp;}//判断是否为nullpublic boolean isEmpty(){if (usedSize 0){return true;}return false;}总程序
public class Heap {public int[] elements;// 底层数组public int usedSize;// 有效元素个数// 构造方法public Heap(){// 数组初始化容量this.elements new int[10];}// 创建堆获取 输入数组 的 数据public void creationHeap(int[] array){this.usedSize array.length;if(isFull()){this.elements Arrays.copyOf(this.elements,this.elements.length*2);}this.elements Arrays.copyOf(array,array.length);for(int parent (this.usedSize -1 - 1)/2 ;parent 0;parent--){// 向下调整shiftDown(parent,this.usedSize);}}// 向下调整public void shiftDown(int parent,int len){int child parent * 2 1;// 左孩子// 能进入该循环说明 这个 parent 只少有一个孩子。while(child len){// 获取 左右孩子的最大值if(child1 len this.elements[child] this.elements[child1]){child;}// 判断 孩子最大值 是否 比 双亲节点 val 值 大// 如果大就需要进行交换if(this.elements[child] this.elements[parent]){int tmp elements[child];elements[child] elements[parent];elements[parent] tmp;// 见附图parent child;child parent * 2 1;}else{break;}}}// 入队操作public void offer(int val){if(isFull()){// 扩容this.elements Arrays.copyOf(this.elements,this.elements.length * 2);}elements[usedSize] val;//usedSize;shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1}private void shiftUp(int child){int parent (child - 1)/2;while(child 0){if(this.elements[child] this.elements[parent]){int tmp this.elements[child];this.elements[child] this.elements[parent];this.elements[parent] tmp;child parent;parent (child - 1) / 2;}else{break;}}}// 判断队列满没满public boolean isFull(){return this.usedSize this.elements.length;}// 出队操作public int poll(){if(isEmpty()){throw new RuntimeException(优先级队列为空);}int tmp this.elements[0];this.elements[0] this.elements[this.usedSize -1];this.elements[this.usedSize - 1] tmp;this.usedSize--;shiftDown(0,usedSize);return tmp;}// 判断队列 空不空public boolean isEmpty(){return this.usedSize 0;}public int peek(){if(isEmpty()){throw new RuntimeException(优先级队列为空);}return this.elements[0];}}
四、校招 – TopK问题
问题描述
从arr[1, n]这n个数中找出最大的k个数这就是经典的TopK问题。从100万中找出最大的k个数
栗子
从arr[1, 12]{5,3,7,1,8,2,9,4,7,2,6,6} 这n12个数中找出最大的k5个。 总结 1、如果求前K个最大的元素要建一个小根堆。 2、如果求 前K个最小的元素要建一个大根堆。 3、如果是求第k大的元素建一个小堆小根堆 堆顶的元素就是第k大的元素。 4、如果是求第k小的元素建一个大堆大根堆 堆顶的元素就是第k小的元素。 五、堆的其他应用-堆排序 1、将数据调整为 大根堆、 2、0 下标 与 最后一个未排序的元素进行交换即可。 3、循环上述两个操作直至 最后一个未排序的元素 下标为 0.。 /*** 堆排序*/public void heapSort(){int last usedSize - 1;while (last 0){int tmp elem[0];elem[0] elem[last ];elem[last ] tmp;shiftDown1(0,last);last --;}}/***向下调整* param parent* param len*/public void shiftDown1(int parent,int len){int child parent * 2 1;// 左孩子// 能进入该循环说明 这个 parent 只少有一个孩子。while(child len){// 获取 左右孩子的最大值if(child1 len this.elem[child] this.elem[child1]){child;}// 判断 孩子最大值 是否 比 双亲节点 val 值 大// 如果大就需要进行交换if(this.elem[child] this.elem[parent]){int tmp elem[child];elem[child] elem[parent];elem[parent] tmp;parent child;child parent * 2 1;}else{break;}}}
