精华内容
下载资源
问答
  • java实现小根堆
    2021-03-13 19:50:18

    1. 堆

    堆是完全二叉树的数组形式,由于堆没有指针指向,所以可以利用下标来模拟指向,假设 i 为父节点,那么 2i+1 为左孩子,2i+2 为右孩子。假设 i 为当前节点,那么 (i - 1) / 2 为父节点

    根据大小排序可分为小根堆和大根堆,小根堆即元素越小越在上方,大根堆则相反。这里注意:元素大小并不是按数组下标来排序的,下图的数字对应数组的坐标

    3135191490aea9836c1be176901ad1aa.png

    堆的应用:

    堆排序

    优先级队列

    快速找最值

    2. 小根堆实现

    内部操作有:

    上浮:将小的元素往上移动、当插入元素时,将元素插入末尾,这样上移即可调整位置

    下沉:将大的元素向下移动、当删除元素时,将首位交换,弹出尾部,首部下移即可调整位置

    插入:添加元素

    弹出:删除元素

    主要是其插入弹出的思想,还有调整时注意下标,因为大小与下标相差1

    package heap;

    // 小根堆时间复杂度是O(1) ~ O(logn)

    // 默认O(nlogn)

    public class Heap {

    // 实际存放元素个数

    // 这里是个坑,debug了好久,起因:下标 = 实际大小-1

    private int size;

    // 数组存储元素

    // 可以实现简单扩容,size++ > capacity时

    // data = copyOf(data,capacity*2);

    private int[] data = new int[10];

    // 交换,传入下标

    private void swap(int a, int b) {

    int temp = data[a];

    data[a] = data[b];

    data[b] = temp;

    }

    // 较大的下沉

    // 将当前节点与其较小儿子交换

    // 并将更新当前节点为交换的儿子节点

    public void fixDown(int index) {

    int son = index * 2 + 1;

    while (son <= size) {

    if (son + 1 < size && data[son + 1] < data[son]) {

    son++; // 这里这要比较左右孩子谁小

    }

    if (data[index] < data[son]) {

    break; // 当前节点比孩子节点小,不用下沉退出循环

    } else {

    swap(index, son);

    index = son;

    son = index * 2 + 1;

    }

    }

    }

    // 较小的上浮

    // 当前节点与父节点相比,若小于则交换,且将当前节点跟新为其父节点

    public void fixUp(int index) {

    int father = (index - 1) / 2;

    while (father >= 0) {

    // 这里卡死一次,debug后发现,只有一个元素会相等进入无限交换

    if (data[index] >= data[father]) {

    break; // 其父节点大于当前节点,不用上浮退出循环

    } else {

    swap(index, father);

    index = father;

    father = (index - 1) / 2;

    }

    }

    }

    // 插入

    // 每次都在最后一个插入,然后上浮到合适位置

    public Heap push(int value) {

    data[size] = value;

    fixUp(size++);

    return this;

    }

    // 弹出根元素

    // 让根元素和尾元素交换,让现在的根元素下沉即可

    public int pop() {

    swap(0, --size);

    fixDown(0);

    return data[size];

    }

    // 测试

    public static void main(String[] args) {

    Heap heap = new Heap();

    // 乱序添加1~9

    // 从输出也可以验证,元素大小并不是按数组小标来排序的

    // 输出:123459786

    heap.push(8).push(5).push(9)

    .push(4).push(2).push(3)

    .push(6).push(7).push(1);

    while(heap.size > 0){

    System.out.print(heap.pop());

    }

    }

    }

    更多相关内容
  • Java实现小根堆和大根堆(PriorityQueue)

    千次阅读 2020-06-28 08:23:01
    1、小根堆实现 package test; import java.util.Comparator; import java.util.PriorityQueue; /* add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常 remove 移除并返回队列头部的元素 如果...

    Java里面的PriorityQueue底层默认使用的堆,所以我们使用PriorityQueue就能实现堆的功能。

    1、小根堆实现

    package test;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /*
        add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
        remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
        element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
        offer 添加一个元素并返回true 如果队列已满,则返回false
        poll 移除并返问队列头部的元素 如果队列为空,则返回null
        peek 返回队列头部的元素 如果队列为空,则返回null
     */
    public class Test {
    
        public static void main(String[] args) {
    
            PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            });
    
            for(int i = 10; i >= 0; i--){
                if(priorityQueue.size() < 5){
                    priorityQueue.add(i);
                }else {
                    priorityQueue.remove();
                    priorityQueue.add(i);
                }
            }
    
            while (!priorityQueue.isEmpty()) {
                System.out.println(priorityQueue.remove());
            }
        }
    }
    

    2、大根堆

    package test;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /*
        add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
        remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
        element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
        offer 添加一个元素并返回true 如果队列已满,则返回false
        poll 移除并返问队列头部的元素 如果队列为空,则返回null
        peek 返回队列头部的元素 如果队列为空,则返回null
     */
    public class Test {
    
        public static void main(String[] args) {
    
            PriorityQueue<Integer>priorityQueue = new PriorityQueue<>();
    
            for(int i = 0; i < 10; i++){
                if(priorityQueue.size() < 5){
                    priorityQueue.add(i);
                }else {
                    priorityQueue.remove();
                    priorityQueue.add(i);
                }
            }
    
            while (!priorityQueue.isEmpty()) {
                System.out.println(priorityQueue.remove());
            }
        }
    }
    

     

    展开全文
  • Java实现小根堆

    千次阅读 多人点赞 2019-01-11 10:50:45
    文章目录1、二叉堆2、一个例子2.1 生成完全二叉树:2.2、调整为小根堆2.3、插入元素2.4、取出堆顶元素2.5、Java代码3、画图工具 1、二叉堆 什么是二叉堆? 二叉堆本质上是一种完全二叉树,它分为两个类型: 1....

    1、二叉堆


    首先参考了一下 → \rightarrow 什么是二叉堆? 此博客也是在看了这篇微信推文的基础上写的。

    什么是二叉堆?

    二叉堆本质上是一种完全二叉树,它分为两个类型:
    1.最大堆
    2.最小堆

    什么是最大堆呢?最大堆任何一个父节点的值,都大于等于它左右孩子节点的值。

    在这里插入图片描述

    什么是最小堆呢?最小堆任何一个父节点的值,都小于等于它左右孩子节点的值。

    在这里插入图片描述

    二叉堆的根节点叫做堆顶

    最大堆和最小堆的特点,决定了在最大堆的堆顶是整个堆中的最大元素;最小堆的堆顶是整个堆中的最小元素。

    2、一个例子


    一个二叉堆的操作大致有三种,
    1. 调整堆
    2. 插入元素
    3. 取出堆顶元素

    假设给我的一串数字是:【10 2 4 21 15 13 18 7 11】 ,即:

    int[] a = new int[] {10,2,4,21,15,13,18,7,11};
    

    下面过一遍堆的调整、插入和取出。提醒一点,向上调整只比较一次,向下调整比较两次。 下面会有提到。

    2.1 生成完全二叉树:


    对于任何一个序列,我们所需要做的是先把它当作一颗完全二叉树,就是下面这样子。

    在这里插入图片描述

    2.2、调整为小根堆


    堆调整是向下调整, 从后往前依次调整每棵子树,每次调整时需要比较两次,子节点之间一次,较小的(对小根堆来说)子节点和根节点之间一次。

    先在最后一颗子树上调整:

    在这里插入图片描述
    比较子节点。7更小一点。

    在这里插入图片描述

    于是721比较,发现721更小。调换两个节点的值。

    在这里插入图片描述

    往上,调整前一颗子树。比较子节点,1318比较,13小。13再与4比较,4小。于是此子树也不需要做调整。

    在这里插入图片描述

    再往上,还是无需调整。

    在这里插入图片描述

    再往上,2较小,210比较。这里我没提子节点之间的比较了,其实是有的,下面也都一样,省略了。不懂我说什么可以前翻一下下黄字处。

    在这里插入图片描述

    10换下来。同理,710比较。

    在这里插入图片描述

    7小。调整节点。

    在这里插入图片描述

    10小。至此小根堆就调整好了。

    在这里插入图片描述

    调整完后,输出的序列应为:【2 7 4 10 15 13 18 21 11】。

    2.3、插入元素


    插入是堆调整中唯一往上调整的一个环节, 刚才说了,往上调整只比较一次,因为插入时,堆已经调整好了,父节点一定是比子节点小的。任一向上调整环节,如果插入的节点小于父节点,交换两个节点,否则调整结束。

    假设插入一个1。先把1插在完全二叉树的末尾,再依次向上调整调整。如果小于父节点,便与父节点交换,直到小于时停止。

    在这里插入图片描述

    1与15比较并调整。

    在这里插入图片描述

    1与7比较并调整。

    在这里插入图片描述

    1与2比较并调整。

    在这里插入图片描述

    插入完成。

    在这里插入图片描述

    插入1完成后的序列为:【1 2 4 10 7 13 18 21 11 15】。

    2.4、取出堆顶元素


    堆只能从堆顶取元素。对于小根堆,每次取出的元素就是最小的元素。方法就是用堆中最后一个元素,覆盖堆顶元素,然后去掉最后一个元素。再次从上往下调整。同样,每次调整比较两次

    15覆盖1,并去掉15。

    在这里插入图片描述

    15比较小的子节点2小,所以向下调整。

    在这里插入图片描述

    15比较小的子节点7小,所以向下调整。因为已经被调整到了页节点上,所以停止。

    在这里插入图片描述

    取出小根堆堆顶元素后的序列为:【2 7 4 10 15 13 18 21 11 】。

    2.5、Java代码


    import java.rmi.dgc.*;
    import javax.lang.model.element.*;
    
    class HeapOperator { //实现的是一个小根堆
    	public static void Adjust(int a[]){
    		int len = a.length;
    		int[] b = new int[len];
    		int FatherNodeNum = len / 2;
    		if(len % 2 == 0){//如果数组a的长度为偶数
    			if(a[len - 1] < a[FatherNodeNum - 1]){//父节点大于子节点
    				int tmp = a[len - 1];
    				a[len - 1] = a[FatherNodeNum - 1];
    				a[FatherNodeNum - 1] = tmp;
    			}
    			--FatherNodeNum;
    		}
    		//下面的每个父节点都有两个子节点
    		while (FatherNodeNum > 0) {
    			int k = FatherNodeNum; //k一直跟着当前的节点,直到此节点被换到叶子结点上
    			while (k <= len / 2) { //len/2 - 1是第一个叶节点的下标
    				int lNode = 2 * k - 1; //左子节点下标
    				int rNode = 2 * k; //右子节点下标
    				if(a[lNode] <= a[rNode]){//如果左子节点小于等于右子节点
    					if (a[lNode] < a[k - 1]) { //同时左子节点小于父节点
    						int tmp = a[lNode];  
    						a[lNode] = a[k - 1];
    						a[k - 1] = tmp;
    						k = 2 * k; //记下此节点是数组中第几个值
    					}
    					else { //如果父节点不小于最小的子节点的值 跳出循环
    						break;
    					}
    				}
    				else { //若右节点更小一点
    					if (a[rNode] < a[k - 1]) { //如果右子节点小于父节点
    						int tmp = a[rNode];
    						a[rNode] = a[k - 1];
    						a[k - 1] = tmp;
    						k = 2 * k + 1; //记下此节点是数组中第几个值
    					}
    					else { //如果父节点不小于最小的子节点的值 跳出循环
    						break;
    					}
    				}
    			}
    			--FatherNodeNum;
    		}
    	}
    	
    	public static int[] InsertNode(int a[],int m){//先实现的简单一点,假设a数组不为空
    		int len = a.length + 1;
    		int[] b = new int[len];
    		System.arraycopy(a, 0, b, 0, len - 1); //将数组a的内容拷贝到b中
    		b[len - 1] = m;//b数组的最后一个元素先赋值为m
    		int k = len; //k-1就是新加入的节点的父节点
    		while(k > 1){ //k为根节点的时候停下来
    			if (b[k - 1] >= b[k/2 - 1]) { //若加入的节点不小于其父节点
    				break; //直接跳出循环
    			}
    			else {//否则交换一下子节点和父节点的值
    				int tmp = b[k - 1];
    				b[k - 1] = b[k/2 - 1];
    				b[k/2 - 1] =tmp; 
    				k = k/2;
    			}
    		}
    		return b;
    	}
    	
    	public static int[] FetchNode(int a[]){
    		int len = a.length - 1;
    		int[] b = new int[len];
    		System.arraycopy(a, 0, b, 0, len); //把a数组的前len-1给赋给b
    		b[0] = a[a.length - 1]; //去除a的最小元素,为保持树状,覆盖第一个元素
    		int k = 1; //现在要把二叉堆从上到下调整
    		while(k <= len / 2){ //k为叶节点的时候停下来
    			int lNode = 2*k - 1; //左子节点的下标
    			int rNode = 2*k; //右子节点的下标
    			if(b[lNode] <= b[rNode]){
    				if (b[lNode] < b[k - 1]) {
    					int tmp = b[lNode];
    					b[lNode] = b[k - 1];
    					b[k - 1] = tmp;
    					k = 2*k;
    				}
    				else {
    					break; //当此节点不小于任何一个子节点的时候,他也会跳出循环
    				}
    			}
    			else {
    				if (b[rNode] < b[k - 1]) {
    					int tmp = b[rNode];
    					b[rNode] = b[k - 1];
    					b[k - 1] = tmp;
    					k = 2*k + 1;
    				}
    				else {
    					break; //当此节点不小于任何一个子节点的时候,他也会跳出循环
    				}
    			}
    		}
    		return b;
    	}
    	
    	public static void main(String[] args) {
    		int[] a = new int[] {10,2,4,21,15,13,18,7,11};
    		Adjust(a); //将其调整为小根堆
    		int i = 0;
    		System.out.print("调整过后的小根堆为:");
    		while (i < 9) {
    			System.out.print(a[i]+" ");
    			++i;
    		}
    		System.out.print("\n");
    		int[] b = new int[a.length + 1];
    		b = InsertNode(a, 1); //在小根堆里面插入一个1
    		i = 0;
    		System.out.print("插入1后的小根堆为:");
    		while (i < 10) {
    			System.out.print(b[i]+" ");
    			++i;
    		}
    		System.out.print("\n");
    		int[] c = new int[a.length];
    		c = FetchNode(b);
    		i = 0;
    		System.out.print("取出小根堆最小元素后的小根堆:");
    		while (i < 9) {
    			System.out.print(c[i]+" ");
    			++i;
    		}
    		System.out.print("\n");
    	}
    }
    

    运行结果:

    调整过后的小根堆为:2 7 4 10 15 13 18 21 11
    插入1后的小根堆为:1 2 4 10 7 13 18 21 11 15
    取出小根堆最小元素后的小根堆:2 7 4 10 15 13 18 21 11

    3、画图工具


    写这篇博文主要是最近可能要用Java编程,所以提前练练手,但是又引发了我一直没有解决的问题。程序员画流程图一般都用什么工具? 我网上找了一下,最后集大家的智慧找到了draw.io 。这是一款在线画图软件,支持各种格式的导出,包括html、xml、PDF等等,也支持中文并且完全免费,这里我都是导出为png格式。下面给一张截图。

    在这里插入图片描述

    可能截图看不太清,想了解的可以自己再找找资料,试试看好不好用。

    好了,老铁们,到这趴~~

    展开全文
  • 主要介绍了Java实现堆排序(大根)的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着编来一起学习学习吧
  • 堆排序(小根堆)的简单实现(java)

    千次阅读 2022-04-09 15:53:21
    实现步骤: 1、构造; 2、得到顶元素,这个值就是最大值; 3、交换顶元素和数组中的最后一个元素,此时所有元素中的最大元素已经被放到合适的位置 4、对进行调整,重新让除了最后一个元素的的剩余元素中...

    堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素。

    堆的定义如下:n个关键字序列L[1...n]称为堆,当且仅当该序列满足:

    1、L(i)<=L(2i)且L(i)<=L(2i+1) 或

    2、L(i)>=L(2i)且L(i)>=L(2i+1) (1<=i<=n/2)

    满足第一种情况的称为小根堆(小顶堆,即最小的元素在根结点);

    满足第二种情况的称为大根堆(大顶堆,即最大的元素在根结点)

    实现步骤:

    1、构造堆;

    2、得到堆顶元素,这个值就是最大值;

    3、交换堆顶元素和数组中的最后一个元素,此时所有元素中的最大元素已经被放到合适的位置

    4、对堆进行调整,重新让除了最后一个元素的的剩余元素中的最大值放到堆顶;

    5、重复2-4这个步骤,直到堆中剩一个元素为止

    api设计:

    实现代码

    package com.yyy;
    
    public class HeapSort<T extends Comparable<T>> {
        //判断heap堆中索引i处的元素是否小于索引j处的元素
        private static  boolean less(Comparable[] heap, int i, int j) {
            return heap[i].compareTo(heap[j])<0;
        }
    
        //交换heap堆中i索引和j索引处的值
        private static  void exch(Comparable[] heap, int i, int j) {
            Comparable tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
        }
    
    
    
        //根据原数组source,构造出堆heap
        private static void createHeap(Comparable[] source, Comparable[] heap) {
            //把source中的元素拷贝到heap中,heap中的元素就形成一个无序的堆
            System.arraycopy(source,0,heap,1,source.length);
    
            //对堆中的元素做下沉调整(从长度的一半处开始,往索引1处扫描)
            for (int i = (heap.length)/2;i>0;i--){
                sink(heap,i,heap.length-1);
            }
    
        }
    
    
    
        //对source数组中的数据从小到大排序
        public static  void sort(Comparable[] source) {
            //构建堆
            Comparable[] heap = new Comparable[source.length+1];
            createHeap(source,heap);
            //定义一个变量,记录未排序的元素中最大的索引
            int N = heap.length-1;
            //通过循环,交换1索引处的元素和排序的元素中最大的索引处的元素
            while(N!=1){
                //交换元素
                exch(heap,1,N);
                //排序交换后最大元素所在的索引,让它不要参与堆的下沉调整
                N--;
                //需要对索引1处的元素进行对的下沉调整
                sink(heap,1, N);
            }
    
            //把heap中的数据复制到原数组source中
            System.arraycopy(heap,1,source,0,source.length);
    
        }
    
    
        //在heap堆中,对target处的元素做下沉,范围是0~range
        private static void sink(Comparable[] heap, int target, int range){
    
            while(2*target<=range){
                //1.找出当前结点的较大的子结点
                int max;
                if (2*target+1<=range){
                    if (less(heap,2*target,2*target+1)){
                        max = 2*target+1;
                    }else{
                        max = 2*target;
                    }
                }else{
                    max = 2*target;
                }
    
                //2.比较当前结点的值和较大子结点的值
                if (!less(heap,target,max)){
                    break;
                }
    
                exch(heap,target,max);
    
                target = max;
            }
        }
    }
    

    测试代码:

    public static void main(String[] args) {
            //待排序数组
            String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};
            //通过HeapSort对数组中的元素进行排序
            HeapSort.sort(arr);
            //打印排序后数组中的元素
            System.out.println(Arrays.toString(arr));
        }

    展开全文
  • 主要介绍了java 实现最小二叉树排序的实例的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
  • java大根堆和小根堆

    2022-02-21 19:20:18
    java使用优先队列实现大顶堆和顶堆,默认是小根堆,当然记不住默认也没有关系 小根堆创建 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a-b); 大根堆创建 ...
  • NULL 博文链接:https://yunjiechao-163-com.iteye.com/blog/2405056
  • 使用 Java 实现优先队列(小根堆

    千次阅读 2020-04-16 23:33:47
    使用 Java 实现优先队列优先队列基本模型优先队列的实现基于链表实现基于二叉查找树实现基于堆实现二叉(binary heap)开始实现一个支持泛型的优先队列属性插入一个元素建 优先队列基本模型 优先队列的基本模型...
  • java使用PriorityQueue即优先队列实现大根堆和小根堆
  • Java 中的大根堆和小根堆

    千次阅读 2019-09-02 22:34:15
    小根堆和大根堆 **完全二叉树:**完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时...
  • Java实现最小

    千次阅读 2020-08-01 17:01:37
    在最小中,它首先是一颗完全二叉树,并且节点的值,要比左右孩子的值都要,同时,左右子树也是最小。本文包含的操作如下: (1)插入一个节点 (2)删除顶元素,也就是删除最小值 (3)通过给定的一...
  • Java的优先队列默认是小根堆 import java.util.PriorityQueue; public class Zz { public static void main(String[] args) throws Exception{ PriorityQueue<Integer>a=new PriorityQueue<>(); ...
  • 小根堆(Heap)的详细实现

    千次阅读 2021-05-24 04:53:41
    的介绍Heap是一种数据结构具有以下的特点:1)完全二叉树2)heap中存储的值是偏序Min-heap: 父节点的值小于或等于子节点的值Max-heap: 父节点的值大于或等于子节点的值的存储一般都用数组来表示,i结点的父结点...
  • 主要介绍了java堆排序原理与实现方法,结合实例形式分析了java堆排序的相关原理、实现方法与操作注意事项,需要的朋友可以参考下
  • PriorityQueue是Java中内置的数据结构,表示堆。 PriorityQueue类继承于抽象类AbstractQueue,而AbstractQueue类实现了Queue... // 默认为小根堆 Queue<Integer> a = new PriorityQueue<>(); System
  • 本篇文章主要介绍了排序的简介,定义,算法实现以及排序的性质。想要了解的朋友可以参考下
  • 首先,明确概念:堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)...借助类PriorityQueue 可以实现小根堆和大根堆。对于PriorityQueue ,观察帮助文档,可以发现,这是jdk1.5以后引...
  • java堆排序算法(小根堆

    千次阅读 2016-12-30 20:33:10
    这几天学习排序算法,主要是引用老师的方法进行编写的,通过多线程和管道通信(即java的PipedInputStream和PipedOutputStream)来实现大量数据的排序 1、首先是将数据分割成nsorters(16、32、64、……)块,对每...
  • Java实现最小

    2016-06-30 23:09:00
    Java实现最小是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。  最大和最小是 二叉 的两种形式。   最大 结点的键值是所有...
  • Java实现堆(最大

    千次阅读 2020-10-16 17:34:26
    1、什么是 现在有这么一个需求,设计一个结构,满足两个操作要求: 删除时,返回该结构的最大值或者最小值的元素 往结构中新增元素 问题:如何组织优先这种结构? 一般数组、链表? 有序数组或者链表? 二叉...
  • 将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。 1.用优先队列实现 一般我们直接用优先队列实现堆: // 顶堆,以 Integer 为例 PriorityQueue<Integer> pq = new PriorityQueue<...
  • 大根堆Java实现

    千次阅读 2022-03-26 11:41:12
    自行百度,这里仅仅提供实现的思路 import java.util.Arrays; // 大根建立 // 核心方法:heapInsert和heapify /** * 插入元素时候:上升 * 删除元素时候:下沉 * 排序和删除相关 */ public class BigHeap{...
  • 最小 最小数据结构也是一棵完全二叉树(叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中...因此节点是数组中的最小值,这即是最小。 下面最小实现: //最小 public class MinHea
  • Java实现堆排序及详细图解

    千次阅读 2021-08-23 11:39:12
    文章目录排序前言实现步骤代码实现 排序 前言 排序(HeapSort)是指利用这种数据结构所设计的一种排序算法。堆积是一个近似于完全二叉树的结构,同时满足子节点的键值总是小于(或者大于)其父节点。 每个...
  • Java的底层结构实现

    千次阅读 2021-12-16 17:56:10
    2、通常用数组来实现,将二叉树的结点按照层级顺序放入数组中,结点在位置1,它的子结点在位置2和3,而子结点的子 结点则分别在位置4,5,6和7,以此类推。 如果一个结点在数组中的索引为k,则它的父结点的索引为k...
  • 下面对Java中的栈、队列、小根堆和大根堆做一个简单的介绍。 它们都有共用的collections接口中定义的常见函数isEmpty(),可以判断该数据结构中是否还有元素。 栈 Java中有Stack类,但现在已经过时了,不推荐使用。一...
  • java中的堆实现

    2020-06-29 16:14:34
    java中的堆实现 如图: 对于java中的,我们使用数组来实现 可以看出,通过一个节点在数组中的索引计算出它的父节点及左右孩子节点的索引。 //返回左节点 public int left(int i) { return (i + 1) * 2 - 1; } /...
  • Java 堆排序(大根堆及小根堆

    千次阅读 2017-12-21 16:24:36
    整理网上的最大及最小代码public abstract class Sorter { public abstract void sort(int[] array); }public class HeapSorter extends Sorter { @Override public void sort(int[] array) { heapSort(arr

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 75,292
精华内容 30,116
关键字:

java实现小根堆