中国网站空间,企业网银怎么登录,哪家公司网站制作好,长春建设股份有限公司堆#xff08;Heap#xff09;#xff1a;堆可以看做是一颗用数组实现的二叉树#xff0c;所以它没有使用父指针或者子指针。堆根据“堆属性”来排序#xff0c;“堆属性”决定了树中节点的位置。 堆的特性
1.堆是完全二叉树#xff0c;除了树的最后一层节点不需要是满的…堆Heap堆可以看做是一颗用数组实现的二叉树所以它没有使用父指针或者子指针。堆根据“堆属性”来排序“堆属性”决定了树中节点的位置。 堆的特性
1.堆是完全二叉树除了树的最后一层节点不需要是满的其它的每一层从左到右都是满的如果最后一层节点不是满的那么要求左满右不满。 2.它通常用数组来实现
具体方法就是将二叉树的节点按照层级顺序放入数组中根结点在位置1它的子节点在位置2和3而子节点的子节点则分别在位置4、5、6和7以此类推。 比如一个节点的位置为k则它的父节点的位置为k/2而它的两个子节点的位置分别为2k和2k1。这样在不使用指针的情况下可以通过数组的索引在树中上下移动向上一层就令k为k/2向下一层就令k等于2k或者2k1. insert插入方法的实现
由于堆是用数组完成数据元素的存储由于数组的底层是一串联系的内存地址所以从数组索引依次往后存放数据但堆中的元素的顺序是有要求的每一个结点的数据要大于等于它的两个子节点的数据注意这点和树的方式不同所以每次插入一个元素都会使得堆中的数据顺序变乱这个时候就需要额外的方法将刚插入的数据放入和合适的位置。 所以如果往堆中插入新元素我们只需要不断的比较新节点k和它的父节点k/2的大小然后根据结果完成元素的交换来实现堆的有序调整。
代码实现
//判断堆中索引i处的元素是否小于索引j处的元素private boolean less(int i,int j){return items[i].compareTo(items[j])0; //i如果小于j compaerto结果就为负数 --那么就返回true}//交换堆中的i索引和j索引处的值private void exchange(int i,int j){T tempitems[i];items[i]items[j];items[j]temp;}/*** 插入元素方法*/public void insert(T t){items[N]t; //先的原因是 此处数组索引0处 不存储元素 从索引1开始swim(N);}/*** 元素浮动方法* 时元素上浮到合适的位置*/public void swim(int k){while (k1){//索引1表示根节点 如果浮动到根节点 那么就不需要再浮动了if (less(k/2,k)){ //如果插入元素比父节点大那么就需要交换//父节点比子节点小 那么就需要交换exchange(k/2,k);}kk/2; //然后使k上浮一层 进入下一次判断}} deleteMax删除最大值方法的实现 由堆的特性可以知道索引1处的元素也就是根节点就是最大的元素当我们把根节点的元素删除后需要有一个新的根节点出现这时候可以暂时把堆中的最后一个元素放到索引1处暂时充当根节点但是这样有可能不满足堆的有序性要求这时候就需要通过元素下沉让新的根节点放入到合适的位置。 所以删除最大元素后只需要将最后一个元素放到索引1处并不断拿当前节点k与它的子节点2k和2k1比较然后与较大者交换位置即可完成堆的有序性调整。 代码实现
/*** 删除最大值 也就是根节点*/public T deleteMax(){T maxitems[1]; //索引1处为根节点exchange(1,N); //索引1根节点 与最后一个节点交换items[N]null;N--;slink(1);return max;}/*** 元素下沉**/public void slink(int k){while (2*kN){ //当2*kN时 就表示该k节点没有子节点了 跳出循环int max; //找到两个子节点中最大的if (2*k1N){ //如果存在右子节点if (less(2*k,2*k1)){//比较两个子节点max2*k1;}else {max2*k;}}else { //如果不存在右子节点 那么只有左子结点的情况max2*k;}//到此两个子节点中的较大者已经比较出 然后将将其比较 如果需要交换的节点比较大者要大 那么就可以结束循环if (!less(k,max)){return;}//如果当前节点 比大子节点小 那么就进行交换exchange(k,max);kmax;}}
测试结果
public static void main(String[] args) {HeapString heap new HeapString(20);heap.insert(A);heap.insert(B);heap.insert(C);heap.insert(D);heap.insert(E);heap.insert(F);heap.insert(G);
// heap.insert(A);
// heap.insert(T);
// heap.insert(P);
// heap.insert(R);String del;while((delheap.deleteMax())!null){System.out.print(del,);}}
//运行结果
G,F,E,D,C,B,A,
