精华内容
下载资源
问答
  • 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

    千次阅读 2013-07-20 11:02:07
    首先什么是小根堆: (1)它一颗完全二叉树 (2)任意一个节点均小于或等于其左右子节点的关键码(大根堆相反就是了) 因此可以得知,当前树形结构的根节点就是当前整个树形结构最小的节点。。。 至于说...

    晚上睡不好觉白天效率就不行,昨天就已经把小根堆的代码写好了,但是因为没什么状态,文章拖到了今天才写。。

    首先什么是小根堆:

    (1)它是一颗完全二叉树

    (2)任意一个节点均小于或等于其左右子节点的关键码(大根堆相反就是了)

    因此可以得知,当前树形结构的根节点就是当前整个树形结构最小的节点。。。


    至于说这种堆结构有什么作用:

    (1)以前本科的时候上数据结构课的时候就有讲过堆排序,好像还不错,O(nlogn)的复杂度

    (2)可以用来构造优先权队列。。。。

    (3)在libevent库中,定时是采用小根堆来维护(nginx是红黑树)


    好了,下面来看看小根堆的插入和删除吧,其实感觉 非常简单诶,比红黑树简单,只需要向上向下浮动就好了,没有红黑树那种左旋右旋,还得染色什么的。。

    首先来看节点的插入:

    (1)将要插入的节点按照完全二叉树的形式插入到当前树形结构的最末尾

    (2)对这个刚刚插入的节点进行向上浮动,浮动的原理是:比较当前的节点和其父节点,如果比父节点小,那么与父节点交换,然后递归的进行,直到浮动不动了或者到了根节点


    接下来来看节点的删除:

    (1)小根堆的删除是删除当前的根节点,也就是返回当前根节点的值,然后用当前树形结构的最后一个节点来代替根节点

    (2)从当前属性结构的最后一个非叶节点开始,向下浮动,浮动的原理是:

       如果有比自己小的子节点,那么与这个子节点交换,然后递归的对刚刚交换下去的子节点进行向下浮动,(如果当前两个子节点都比自己小,那么就与最小的那个交换)


    好了,小根堆的原理都差不多了,真心觉得蛮简单的,而且效率也都还不错。。。

    下面就是我自己实现的一个小根堆的代码,貌似写的挺挫的。。讲究看吧:

    public class SmallHeap <T>{
    	
    	private Entry<T> root;     //根节点
    	private Entry<T> lastNode;  //当前树的最后一个节点
    	private Entry<T> last;    //最后一个非叶节点
    	private int size;
    	
    	public SmallHeap() {
    		this.root = null;
    		this.size = 0;
    		this.last = root;
    		this.lastNode = root;
    	}
    	
    	public boolean add(T item) {
    		if (this.root == null) {
    			Entry<T> nowNode = new Entry<T>(item, null, null);
    			this.root = this.last = this.lastNode = nowNode;
    			return true;
    		}
    		if (this.last.right != null) {  //表示最后一个非叶节点的子节点已经占满了,那么用下一个节点
    			this.last = this.last.next;
    		}
    		Entry<T> nowNode = new Entry<T>(item, this.last, this.lastNode);
    		
    		this.lastNode.next = nowNode;    
    		this.lastNode = nowNode;
    		
    		if (this.last.left == null) {
    			this.last.left = nowNode;
    		} else {
    			this.last.right = nowNode;
    		}
    		this.siftUp(nowNode);
    		this.size++;
    		return true;
    	}
    	
    	public int size() {
    		return this.size;
    	}
    	
    	public T poll() {
    		if (root == null) {
    			return null;
    		}
    		T out = root.value;
    		root.value = this.lastNode.value;
    		
    		Entry<T> tlast = this.lastNode;
    		if (tlast == root) {
    			this.last = null;
    			this.lastNode = null;
    			this.root = null;
    			return out;
    		}
    		
    		this.lastNode = this.lastNode.before;
    		this.lastNode.next = null;
    		
    		if (tlast == tlast.parent.left) {
    			tlast.parent.left = null;
    			this.last = this.last.before;
    		} else {
    			tlast.parent.right = null;
    		}
    		
    		Entry<T> node = this.last;
    		node = root;
    
    		
    		while (node != null) {
    			this.siftDown(node);
    			node = node.before;
    		}
    		this.size--;
    		return out;
    	}
    	
    	public T top() {
    		if (root == null) {
    			return null;
    		}
    		return root.value;
    	}
    	
    	
    	
    	private void siftDown(Entry<T> node) {
    		if (node == null) {
    			return;
    		}
    		while (node.left != null) {
    			Comparable now = (Comparable) node.value;
    			Comparable child = null;
    			Entry<T> childNode;
    			
    			if (node.right != null) {
    				Comparable child1 = (Comparable) node.left.value;
    				Comparable child2 = (Comparable) node.right.value;
    				
    				if (child1.compareTo(child2) < 0) {
    					child = child1;
    					childNode = node.left;
    				} else {
    					child = child2;
    					childNode = node.right;
    				}
    				
    			} else {
    				child = (Comparable) node.left.value;
    				childNode = node.left;
    				
    			}
    			if (now.compareTo(child) > 0) {
    				node.value = (T)child;
    				childNode.value = (T)now;
    				node = childNode;
    				continue;
    			}
    			
    			
    			
    			break;
    			
    		}
    	}
    	
    	
    	private void siftUp(Entry<T> node) {
    		if (node == null) {
    			return;
    		}
    		while (node.parent != null) {
    			Comparable now = (Comparable) node.value;
    			Comparable parent = (Comparable) node.parent.value;
    			if (now.compareTo(parent) < 0) {
    				node.value = (T)parent;
    				node.parent.value = (T)now;
    				node = node.parent;	
    				continue;
    			}
    			break;
    		}
    	}
    	
    	
    	
    	
    	private final class Entry<T> {
    		Entry<T> parent;  //父亲节点
    		Entry<T> left;
    		Entry<T> right;
    		
    		Entry<T> next;
    		Entry<T> before;
    		
    		T value;
    		
    		public Entry(T value, Entry<T> parent, Entry<T> before) {
    			this.value = value;
    			this.parent = parent;
    			this.before = before;
    		}
    	}
    	
    	public static void main(String args[]) throws IOException {
    		
    		SmallHeap<Integer> s = new SmallHeap<Integer>();
    		int max = 3000000;
    		long before = (new Date()).getTime();
    		for (int i = max; i > 0; i--) {
    			s.add(new Integer((int)(Math.random() * max)));
    		}
    	
    		Integer t = s.poll();
    		while (t != null) {
    			//System.out.println(t.toString());
    			t = s.poll();
    		}
    		long after = (new Date()).getTime();
    		System.out.println(((double)after - (double)before) / 1000);
    
    	}
    }

    展开全文
  • 红黑树与小根堆性能对比(java

    千次阅读 2013-07-20 17:22:44
    因为nginx与libevent采用了不同的数据结构来维护超时事件,其中...小根堆就用前面的那篇文章中自己实现的那个代码,代码比较挫,也没有做什么优化,红黑树通过继承java的TreeMap来实现。。。 测试案例: 向两种结构

    因为nginx与libevent采用了不同的数据结构来维护超时事件,其中nginx采用了红黑树,libevent采用的是小根堆,所以一直比较好奇,这两种数据结构谁在这种应用场景下更合适(当做优先权队列来用)

    好吧,好奇那就试一下就好了。。。

    小根堆就用前面的那篇文章中自己实现的那个代码,代码比较挫,也没有做什么优化,红黑树通过继承java的TreeMap来实现。。。

    测试案例:

    向两种结构中分别放入相同数量的随机数,然后不断的将他们中的最小的节点去取出来。。。。

    其中红黑树的代码如下:

    package Time;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Date;
    import java.util.TreeMap;
    
    public class RbTree<T> extends TreeMap<T, Object>{
    	/**
    	 * 
    	 */
    	private static final long serialVersionUID = 1L;
    	
    	private Object PER = new Object();
    		
    	
    	public void add(T node) {
    		this.put(node, PER);
    	}
    	
    	public T poll() {
    		if (super.size() > 0) {
    			T node = super.firstKey();   //获取当前红黑树最左边的key,也就是最小的key
    			super.remove(node);  //将这个key从树形结构中删除
    			return node;
    		} else {
    			return null;
    		}
    	}
    	
    	
    	public static void main(String args[]) throws IOException {
    		RbTree<Integer> rtTree = new RbTree<Integer>();
    		int max = 1000000;
    		long before = (new Date()).getTime();
    		for (int i = max; i > 0; i--) {
    			rtTree.add(new Integer((int)(Math.random() * max)));
    		}
    	
    		Integer t = rtTree.poll();
    		while (t != null) {
    			//System.out.println(t.toString());
    			t = rtTree.poll();
    		}
    		
    		long after = (new Date()).getTime();
    		System.out.println(((double)after - (double)before) / 1000);
    		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    		reader.readLine();
    	}
    	
    }
    

    其中,分别测试了100万,200万,600万和1000万的数据量。。。

    最后的结论是:

    红黑树的性能比小根堆好(都是近似时间复杂度O(nlogn)  ),一般处理相同的数据量,小根堆需要的时间大概是红黑树的两倍左右,当然这也不排除我写的小根堆代码不行,毕竟红黑树用的代码基本上都是java类库的。。。。。。

    展开全文
  • 二叉堆是一种特殊的堆,可以看做是完全二叉树,它分为两个类型: 1.最大堆 2.最小堆 什么是最大堆呢?就是父结点的键值总是大于或等于任何一个子节点的键值; 什么是最小堆呢?父结点的键值总是小于或等于...

    堆的定义

    二叉堆是一种特殊的堆,可以看做是完全二叉树,它分为两个类型:

                        1.最大堆

                        2.最小堆

             什么是最大堆呢?就是父结点的键值总是大于或等于任何一个子节点的键值;

             什么是最小堆呢?父结点的键值总是小于或等于任何一个子节点的键值。

            其中二叉堆的根节点叫做堆顶。

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

    堆的自我调整

    堆的构建其实就是依靠堆的自我调整,而堆的自我调整有如下几个操作:

      1.  添加节点

      2. 删除节点

      3. 构建二叉堆

    接下来我们以最大堆为例,看看二叉堆是如何自我调整的。

    • 添加节点

      假设在最大堆[90,80,70,60,40,30,20,10,50]种添加85,需要执行的步骤如下:

    如上图所示,当向最大堆中添加数据时:先将数据加入到最大堆的最后,然后将其与父节点做比较,如果大于父节点,就进行“上浮”操作,直到父节点比85大,上浮不动为止。将85添加到[90,80,70,60,40,30,20,10,50]中后,最大堆变成了[90,85,70,60,80,30,20,10,50,40]。

    • 删除节点

    假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90,需要执行的步骤如下:

    从[90,85,70,60,80,30,20,10,50,40]删除90之后,最大堆变成了[85,80,70,60,40,30,20,10,50]。如上图所示,当从最大堆中删除数据时:先删除该数据,然后用最大堆中最后一个的元素插入这个空位;接着,跟子节点中最大的数作比较,如果子节点大,则进行“下沉”操作,直到剩余的数据变成一个最大堆。

    构建二叉堆

    构建二叉堆,也就是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有非叶子节点依次下沉。我们举一个无序完全二叉树的例子:

    堆代码的实现

    在实现代码之前,我们首先要明白

    • 父节点与子节点的关系
      • 假设"第一个元素"在数组中的索引为 0 的话,则父节点和子节点的位置关系如下:
        • (01) 索引为i的左孩子的索引是 (2*i+1);
        • (02) 索引为i的右孩子的索引是 (2*i+2);
        • (03) 索引为i的父结点的索引是 floor((i-1)/2);
    • 代码实现
      package Algorithm;
      
      import java.util.Arrays;
      
      /**
       * 二叉堆的代码实现
       */
      public class TwoForkPile {
          public static void main(String[] args) {
              int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
              upAdjust(array);
              System.out.println(Arrays.toString(array));
              array = new int[] {7,1,3,10,5,2,8,9,6};
              buildHeap(array);
              System.out.println(Arrays.toString(array));
          }
      
          /**
           * 构建二叉堆
           * @param array
           */
          private static void buildHeap(int[] array) {
              // 从最后一个非叶子节点开始,依次下沉调整
              for (int i = (array.length -2 )/ 2; i >= 0; i--) {
                  downAdjust(array, i, array.length);
              }
          }
      
          /**
           * 下沉操作
           * @param array
           * @param parentIndex
           * @param length
           */
          private static void downAdjust(int[] array, int parentIndex, int length) {
              // temp保存父节点值,用于最后的赋值
              int temp = array[parentIndex];
              int childIndex = 2 * parentIndex + 1;
              while (childIndex < length) {
                  // 如果有右孩子,且右孩子大于左孩子的值,则定位到右孩子
                  if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
                      childIndex++;
                  }
                  // 如果父节点大于任何一个孩子的值,直接跳出
                  if (temp >= array[childIndex]){
                      break;
                  }
                  //无需真正交换,单向赋值即可
                  array[parentIndex] = array[childIndex];
                  parentIndex = childIndex;
                  childIndex = 2 * childIndex + 1;
              }
              array[parentIndex] = temp;
          }
      
          /**
           * 上浮操作
           * (增加节点)
           * @param array
           */
          private static void upAdjust(int[] array) {
              int childIndex = array.length-1;            //最后一个叶子元素
              int parentIndex = (childIndex - 1) / 2;     //最后一个非叶子的父节点
      
              int temp = array[childIndex];
              while(childIndex > 0 && temp > array[parentIndex]){
                  array[childIndex] = array[parentIndex];
                  childIndex = parentIndex;
                  parentIndex = (parentIndex-1) / 2;
              }
              array[childIndex] = temp;
          }
      }
      

      参考文献

    • 二叉堆(一)之图文解析和C语言的实现(链接地址:https://www.cnblogs.com/skywang12345/p/3610187.html)

     

    展开全文
  • 红黑树与小根堆性能对比

    千次阅读 2014-06-26 17:37:27
    因为nginx与libevent采用了不同的数据结构来维护超时事件,其中...小根堆就用前面的那篇文章中自己实现的那个代码,代码比较挫,也没有做什么优化,红黑树通过继承java的TreeMap来实现。。。 测试案例: 向两种结构
  • 将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。 堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般...
  • 每个节点的关键字都不大于其子节点的关键字,这种堆称为小根堆。每个节点的关键字都不小于其子节点的关键字,这种堆称为大堆根。本文采用此结构演示综上所述,堆是一棵顺序存储的按照特定规则的完全二叉树。数组的...
  • Java数据结构与算法填坑什么是堆?首先堆是完全二叉树——深度为k,有n个节点,对树中的节点...小根堆:指每个父节点的值都比左右子节点的值小的完全二叉树堆排序的思想以从小到大排序为例:1)把待排序的数组构造成一...
  • Java大根创建和重建及排序

    千次阅读 2018-08-04 23:22:22
    堆又分为大根堆和小根堆,大根堆:在完全二叉树中,任何一个子树的最大值都为该子树的父节点。 小根堆:在完全二叉树中,任何一个子树的最小值都为该子树的父节点。 大根堆的创建与堆排序 堆结构在Java中十分...
  • 首先明确什么是堆? 一个数组: int[] unsort={12,24,35,40,50,66,70,56,55}; 的表现形式(这一个最小节点最小的): 用数组来表示,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为...
  • Java实现排序算法

    2021-02-25 14:05:59
    另一个堆是“最小堆”,这也是一种特殊类型的堆,其值比其子项的值低。我们可以使用堆排序算法对数组值进行排序。在此算法中,将使用生成的堆来重建堆。堆排序的复杂度为O(n.log(n))。堆排序最慢,但对于大型...
  • 了解之前,我们要知道什么是完全二叉树 完全二叉树: 从节点往下,除最后一层外,其余层节点全满 最后一层节点都向左靠拢 比如这样(图解): 在计算机科学中,就有一类数据结构就近似完全二叉树性质,...
  • 每个节点的关键字都不大于其子节点的关键字,这种堆称为小根堆。每个节点的关键字都不小于其子节点的关键字,这种堆称为大堆根。本文采用此结构演示综上所述,堆是一棵顺序存储的按照特定规则的完全二叉树。数组的...
  • 排序+java

    2019-03-01 10:06:06
    其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。 其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。 举例来说,对于n个元素的序列{R0,R1, ... ,Rn}当且仅当满足下列...
  • 反之,则小堆,或者小根堆,或者最小堆。 大堆与小堆可以用于筛选数组之中最大值或是最小值, 比如在千万级别的数据中找到前五个最大的值,那么就要建立一个有五个元素的小堆,每一次筛选,如果筛选的元素比堆顶...
  • java 使用二叉实现 TopK 算法

    千次阅读 2017-05-26 20:19:06
    1.首先,什么是二叉,维基百科上这么描述的: 当父节点的键值总是大于或等于任何一个子节点的键值时为最大。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小。 2.二叉一般用数组来表示。...
  • 堆的结构可以分为大根堆和小根堆一个完全二叉树,而堆排序根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆 性质:每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆;每个...
  • 采用了(一个可以自我调整的二叉树),执行增加删除操作后,可以让最小元素移动到。发表于 2015-12-03 17:06:15回复(5)26PriorityQueue从JDK1.5开始提供的新的数据结构接口,它一种基于优...
  • 排序法(Java实现)

    2018-09-03 17:23:03
     想知道什么是堆排序,就得先知道什么是堆,堆分为两种,大根堆和小根堆什么是大根堆小根堆呢?那你得先知道完全二叉树,什么是完全二叉树?完全二叉树,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的...
  • 例如:小根堆:每个孩子节点的值大于等于其父节点的值。例如:给定一个数组,如何用完全二叉树表示呢?这个数组对应的完全二叉树按层进行编号,其逻辑结构如下图接下来看看堆排序的基本思想:将待排序数组构造成一个...
  • 排序原理(java实现)

    千次阅读 2017-08-18 21:41:35
     想知道什么是堆排序,就得先知道什么是堆,堆分为两种,大根堆和小根堆什么是大根堆小根堆呢?那你得先知道完全二叉树,什么是完全二叉树?完全二叉树,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的...
  • 最近写java程序的时候,经常用到堆这种数据结构,但是java本身的JDK本没有提供这种数据结构的实现。(栈,队列都有,为什么就不...实现的功能有:堆排序,创建大根堆,创建小根堆,增删改查等基本功能。底层运用的数
  • 排序之Java实现

    2015-03-12 16:19:00
    排序思想: ...有了上面的定义,我们能够得知,处于最大节点的元素一定这个中的最大值。事实上我们的排序算法就是抓住了的这一特点,每次都取顶的元素,将其放在序列最后面,然后将...
  • 排序实现(java实现)

    2020-01-13 18:55:40
    首先我们要明确一下堆排序的概念,堆排序就是利用大根堆和小根堆来实现的一种排序方法。 那么什么是堆呢?堆(heap)也被称为优先队列(priority queue)。队列中允许的操作先进先出(FIFO),在队尾插入元素,在...
  • 什么是完全二叉树? 对于一个深度为k,有n个节点的二叉树,其所有的结点与深度为k的满二叉树对应的编号一样,则称之为完全二叉树。 数组如何转成完全二叉树? 举个栗子,有一个数组arr = {1,2,3,4,5},那我们...
  • 堆是一种重要的数据结构,它是一种完全二叉树。堆分为最大堆和最小堆,最大堆任意子树根节点不小于任意子结点,即每一个父节点一定大于其两个左右子节点;最小堆则与之相反,最小堆的节点不大于任意子结点。底层...
  • 排序(java实现)

    2018-06-13 11:36:03
    什么是堆结构? 结构一种树结构,准确说是一种完全二叉树结构。树中的每一个结点对应着原始数据的一个记录,每个结点应满足: 大顶堆:从小到大排列,要求非叶结点的数据要大于等于其左右结点的数据 顶堆:从...
  • 排序详解(java实现)

    2018-07-11 19:42:05
    什么叫堆排序 堆排序(Heapsort)...堆分为大根堆和小根堆完全二叉树。大根堆的要求每个节点的值都不大于其父节点的值,即A[PARENT[i]] &gt;= A[i].什么是完全二叉树 若设二叉树的深度为h,除第 h 层外,...
  • 一、什么是堆排序 排序(Heapsort)指利用这种数据结构所设计的一种排序算法。堆积一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点 二、排序的...
  • 堆分为小根堆和大根堆。对于一个小(大)根堆,它具有如下特征的一棵完全二叉树: 1、若树根结点存在左孩子,则根结点的值小(大)于等于左孩子结点的值。 2、若树根结点存在右孩子,则根结点的值小(大)于等于...

空空如也

空空如也

1 2 3 4
收藏数 62
精华内容 24
关键字:

java小根堆是什么

java 订阅