精华内容
下载资源
问答
  • 创建的方式有两种,一种是一边插入结点,一边调用的插入方法调整堆,这样的时间复杂度就是 O(NlogN),而第二种方式就把时间复杂度缩减到了O(N),它是采用先把结点插入好了,然后再来调整堆,并不是一边插入一边...

    创建堆的方式有两种,一种是一边插入结点,一边调用堆的插入方法调整堆,这样的时间复杂度就是
    O(NlogN),而第二种方式就把时间复杂度缩减到了O(N),它是采用先把结点插入好了,然后再来调整堆,并不是一边插入一边调整。
    但是从代码层面来看,可能会误以为第二种方式的时间复杂度也是O(NlogN),但第二种方式是从下往上建立堆。举个例子,如下所示,假设堆中存在了N个节点(满足堆的性质),采用第一种方式,再创建N个结点,那么插入第一个数时,就调用了时间复杂度为logN的插入方法,插入N个数后,时间复杂度为logN。
    在这里插入图片描述

    让我们看看第二种方式会如何?
    先把N个结点创建到树中,把这N个结点具体化,我们看到在调整树时,第一次是以倒数第二层的结点作为根节点,然后来调整这棵子树,也就是它的时间复杂度不再是logN了,因为远远没到N个结点,远远没到整颗树的高度,它的时间复杂度应该如下判断,在最坏情况下,树中每个结点,会一直向下查找,一直到底,假设树高为h,则倒数第二层会向下查找1次,倒数第三层会向下查找2次…
    倒数第二层结点数为2(h-2),倒数第三层2h-3
    在这里插入图片描述
    在这里插入图片描述

    JAVA代码实现

    import java.util.ArrayList;
    import java.util.Arrays;
    
    //必须传入一个Comparable的实现类,因为后续会用到类的内部比较器
    public class Heap<E extends Comparable> {
        Comparable<? super E>[] list;//堆--存储Comparable的实现类
        int size;  //堆长度
        int capacity;//堆容量
    
        public Heap(int capacity){
            this.capacity=capacity;
            size=0;
            list=new Comparable[capacity+1];
        }
    
        //初始化
        public void Init(E value,int index){
            if(index>0)
            { list[index]= value;
              size++;
            }
            else
                new RuntimeException("下标越界");
        }
    
        //创建堆
        public void Build_Max_Heap(){
           for(int i=size/2;i>0;i--){
               int child=0;
               int parent = i;
               Comparable par_X= (E) list[i];
               for(;parent*2 <= size;parent=child){
                   child=parent*2;
                   if(child+1<=size && list[child].compareTo((E) list[child+1]) ==-1)
                       child++;
                   if(par_X.compareTo((E) list[child])==1)
                       break;
                   list[parent]=list[child];
               }
               list[parent]=(E) par_X;
           }
        }
    
        //插入堆
       public void Insert(E node){
            list[++size]=node;
            for(int i=size;i/2>=0;i=i/2){
                if(i==1 || list[i/2].compareTo((E)node)==1){
                     list[i]=node;
                     break;
                }
                else{
                    list[i]=list[i/2];
               }
            }
       }
    
       //删除堆
       public E Delete(){
            Comparable DeleteX=list[1];
            Comparable X=list[size--];
            int child=1;
            int parent=1;
            for(;parent*2<=size;parent=child){
                child=parent*2;
                if(child+1<=size && list[child].compareTo((E)list[child+1])==-1 )
                    child++;
                if(X.compareTo((E)list[child])==-1)
                    list[parent]=list[child];
                else
                    break;
            }
            list[parent]=X;
            return (E)DeleteX;
       }
    
        //测试数据
        public static void main(String[] args) {
            Heap<SSS> heap = new Heap<>(10);
            heap.Init(new SSS(1),1);
            heap.Init(new SSS(2),2);
            heap.Init(new SSS(3),3);
            heap.Init(new SSS(4),4);
            heap.Init(new SSS(5),5);
            heap.Insert(new SSS(6));
            heap.Build_Max_Heap();
            heap.Delete();
            for(int i=1;i<=heap.size;i++)
                System.out.println(heap.list[i]);
        }
    }
    class SSS implements Comparable {
       int X;
    
        @Override
        public int compareTo(Object o) {
            SSS s2=(SSS) o;
            if(X>s2.X)
                return 1;
            if(X<s2.X)
                return -1;
            else return 0;
        }
        public SSS(int X){
            this.X=X;
        }
    
        @Override
        public String toString() {
            return "SSS{" +
                    "X=" + X +
                    '}';
        }
    }
    
    
    展开全文
  • 的实现2.1的向下调整算法(建小)2.2 向下调整算法(建小)实现2.3 数组建算法(建小)2.4 数组建算法(建小)实现2.5 排序(降序)2.6 排序(降序)实现2.7 建的时间复杂度 1. 大根:所有父节点...

    1.堆

    大根堆:所有父节点大于等于孩子节点
    在这里插入图片描述

    小根堆:所有父节点小于等于孩子节点
    在这里插入图片描述
    堆的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值

    • 堆总是一棵完全二叉树

    2.堆的实现

    堆的实现请点击—> 堆的实现

    现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
    int a[] = {27,15,19,18,28,34,65,49,25,37};

    2.1堆的向下调整算法(建小堆)

    向下调整算法-前提:当前树的左右子树必须都是一个小堆
    向下调整算法的核心思想:选出左右孩子中小的哪一个,跟父亲交换,小的往上浮,大的往下沉,如果要建大堆则相反

    如下图所示为一个向下调整法调小堆
    在这里插入图片描述

    2.2 堆向下调整算法(建小堆)实现

    //堆向下调整算法
    //建小堆
    void AdjustDown(int* a, int n, int root)
    {
    	int parent = root;
    	int child = parent * 2 + 1;
    	//孩子超过数组下标结束
    	while (child < n)
    	{
    		//child始终左右孩子中小的那个
    		if (a[child + 1] < a[child] && child + 1 <n)//防止没有右孩子
    		{
    			++child;
    		}
    		//小的往上浮,大的往下浮
    		if (a[child] < a[parent])
    		{
    			int tem = a[parent];
    			a[parent] = a[child];
    			a[child] = tem;
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		//中途child>parent则已满足小堆,直接break
    		else
    		{
    			break;
    		}
    	}
    }
    

    2.3 堆的向上调整算法

    使用场景:向堆中插入数据,需要使用向上调整算法调整,因为向堆中插入数据是将数据插入到下标为size的位置,此时就不满足小堆(大堆),因此,需要堆其进行调整,向上调整算法和向下调整算法思路类似,此处以小堆为例,向上调整法只需从插入的节点位置开始和父节点比较,若a[chaild]<a[parent],则交换,若a[chaild]>=a[parent]则说明越界满足小堆,直接break

    如下图所示插入一个数据使用向上调整法调整
    在这里插入图片描述

    2.4 向上调整算法(建小堆)实现

    //堆的向上调整算法
    //建小堆
    void AdjustUp(HPDataType* a, int child)
    {
    	int parent = (child - 1) / 2;
    	while (child > 0)
    	{
    		if (a[child] < a[parent])
    		{
    			int tem = a[parent];
    			a[parent] = a[child];
    			a[child] = tem;
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    

    2.5 数组建堆算法(建小堆)

    若左右子树不是小堆——想办法把左右子树处理成小堆
    可以从倒数第一个非叶子节点的位置开始向下调整

    如下图所示可以按图中的步骤依次向下调整
    最后一个非叶子节点的下标为 (n-1-1)/2
    在这里插入图片描述

    2.6 数组建堆算法(建小堆)实现

    	int n = sizeof(a) / sizeof(int);
    	//数组建堆算法
    	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    	{
    		AdjustDown(arr, n, i);
    	}
    

    2.7 堆排序(降序)

    下面我们将上面建好的小堆进行降序排序

    堆排序(降序)的核心思想:因为建小堆可以选出最小的数即根节点,我们将每次建好的小堆的最后一个叶子节点和根节点进行交换,交换后不把最后一个数看作堆里的数据,此时根的左右子树依旧是大堆,然后我们再用向下调整算法选出次小的如此循环直到堆里剩一个数结束

    • 升序建大堆
    • 降序建小堆

    2.8 堆排序(降序)实现

    //降序
    void HeapSort(int* a, int n)
    {
    	//建小堆
    	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    	{
    		AdjustDown(a, n, i);
    	}
    	int end = n - 1;
    	//把最小的换到最后一个位置,不把最后一个数看作堆里的
    	//每次选出剩下数中最小的
    	//从后往前放
    	while (end > 0)
    	{
    		int tem = a[end];
    		a[end] = a[0];
    		a[0] = tem;
    		//选出次小的数
    		AdjustDown(a, end, 0);
    		--end;
    	}
    }
    

    2.9 建堆的时间复杂度

    最坏的情况及满二叉树,且每个节点都需要调整
    在这里插入图片描述
    由以上推论过程可得建堆的时间复杂度为O(N);
    向下调整算法的时间复杂度为O(log2N);
    所以堆排序的时间复杂度为O(N*log2N);

    展开全文
  • 最小堆

    千次阅读 2015-04-23 13:57:46
    该数据结构满足首为中的最小元素,二叉树中的所有父节点都比子节点的要小。 首先要讨论的问题是构建 1从0开始构建,直接一项一项的添加进 这是一个动态添加的过程,每次添加都假设现在的满足最大的...

    一种常见的数据结构,内部用二叉树的结构存储着数据,由于该二叉树满足完全二叉树的定义,所以我们可以通过数组来实现二叉树的存储。该数据结构满足堆首为堆中的最小元素,二叉树中的所有父节点都比子节点的要小。

    首先要讨论的问题是构建堆

    1从0开始构建,直接一项一项的添加进堆

    这是一个动态添加的过程,每次添加都假设现在的堆满足最大堆的定义,每次添加一项我们就需要把它放到合适的位置。一个很初始的想法就是把节点放在完全二叉树的下一个节点上,如果不满足最小堆的定义再调整,此时我们发现冲突点转移到了高度为1层的节点上,那么我们把新添加的节点与父节点比较,如果存在冲突,我们就交换两者位置,此时高度为0与1层的节点之间的关系满足了最小堆定义,此时矛盾转义到了高度为2层的节点上,重复之前的操作,此时我们会发现高度为0,1,2的层满足最小堆的定义,依次我们可以推到树的根节点。  


    2从一个已有数组开始构建

    这里也可以通过动态构建,假设目前数组可以构成一个高度为h的二叉树,我们可以通过从高度为1的最小堆开始构建,然后利用高度为1的最小堆构建高度为2的最小堆,一直到高度为h的最小堆,这个过程中每个分析单元 我们只需要考虑将堆的根节点放到合适的位置,这样新构造的堆肯定能满足最小堆的要求。


    其次要考虑的问题是取元素的过程

    我们需要拿出去的元素肯定是堆首,但是当我们拿出堆首之后,这个堆就存在着一个空槽,我们的问题是怎么填补这个空槽,我一个直接的想法是取子节点中最小的元素来填补空槽,那么空槽就会被推到下一层,但是存在着一个问题,当我们把空槽推到最底层的时候我们要选择哪个元素去填补这个空槽,由于需要满足完全二叉树,那么我们很自然的想到拿出最后一个元素填充这个空槽,但是注意这样填补了可能导致整个堆不满足最小堆的定于,我们需要处理这个元素比父元素大的情况,使他一路上浮到该有的位置,

    这个过程其实是和直接拿最后的元素填充到堆首并且将该元素推到该有的位置是等价的。


    另外需要考虑的就是关于最小堆的一些有意义的操作了,其中一个就是实现优先队列,普通的进队出队操作和最小堆的进堆出堆操作是一致的,剩下需要考虑的就是提高和降低优先级的操作,这个在最小堆中实现也很简单,只是降低或增加排序键值的值,我们可以通过一次线性搜索找到需要操作的对象,然后通过一次堆排序来实现


    对于最小堆来说  进堆操作和出堆操作的时间复杂度都是O(log(n)),也就是元素需要上浮或者下潜log(n)层,但是构建一个最小堆的过程时间复杂度为O(n)  总的来说效率还是很高的


    package 最小堆;
    
    public class MinHeap {
    
    	public static void main(String[] args) {
    		MinHeap minHeap = new MinHeap(7);
    		int[] array = { 4, 3, 2, 1, 5, 7 };
    		int k = 6;
    		minHeap.buildup(array, k);
    		minHeap.addElement(6);
    		minHeap.increasePriority(6, 10);
    		minHeap.decreasePriority(2, 8);
    		minHeap.deleteInnode(3);
    		while(minHeap.hasMore()){
    			System.out.println(minHeap.pushoutHeapHead());
    		}
    	}
    
    	int[] heap; // 0号位弃用 来实现二叉树到数组的映射
    	int heapSize; // 记录堆的大小
    	private int MaxSize; // 记录堆的最大大小
    
    	public MinHeap(int defaultSize) {
    		heap = new int[defaultSize + 1];
    		heapSize = 0;
    		MaxSize = defaultSize;
    	}
    
    	// 把元素向上推到合适位置
    	private void pushUp(int index) {
    		while (index > 1) {
    			if (heap[index] < heap[index >> 1]) {
    				int temp = heap[index];
    				heap[index] = heap[index >> 1];
    				heap[index >> 1] = temp;
    				index = index >> 1;
    			} else {
    				return;
    			}
    		}
    	}
    
    	// 把元素向下推到合适的位置
    	private void pollDown(int index) {
    		int OrNum = -1;
    		if ((index << 1) <= heapSize && heap[index] > heap[index << 1]) {
    			OrNum = 0;
    		}
    
    		if ((index << 1 | 1) <= heapSize && heap[index] > heap[index << 1 | 1]) {
    			if (OrNum > -1 && heap[index << 1] < heap[index << 1 | 1]) {
    
    			} else {
    				OrNum = 1;
    			}
    		}
    		if (OrNum >= 0) {
    			int temp = heap[index];
    			heap[index] = heap[index << 1 | OrNum];
    			heap[index << 1 | OrNum] = temp;
    			pollDown(index << 1 | OrNum);
    		} else {
    			return;
    		}
    	}
    
    	// 传入参数K表示 数组的前k个初始化成堆,另外要求k要小于堆的最大大小
    	// 结果为 最后类中存在着一个大小为K的堆
    	public void buildup(int[] inputArray, int k) {
    		for (int i = 0; i < k; i++) {
    			heap[i + 1] = inputArray[i];
    		}
    		heapSize = k;
    		int index = Integer.highestOneBit(k) - 1;
    		while (index > 0) {
    			pollDown(index);
    			index--;
    		}
    	}
    
    	// 向堆中添加元素
    	public void addElement(int inNum) {
    		heapSize++;
    		heap[heapSize] = inNum;
    		pushUp(heapSize);
    	}
    
    	// 将堆首推出堆
    	public int pushoutHeapHead() {
    		int reVal = heap[1];
    		heap[1] = heap[heapSize];
    		heapSize--;
    		pollDown(1);
    		return reVal;
    	}
    
    	// 辅助取出堆首
    	public boolean hasMore() {
    		return heapSize > 0;
    	}
    
    	// 这个方法是通过key 找到节点,将该节点的优先级降低
    	// 由于目前实现中的key和优先级一致可能不明显,但是可以用这样的结构实现任务调度
    	public void decreasePriority(int key, int value) {
    		for (int i = 1; i <= heapSize; i++) {
    			if (heap[i] == key) {
    				heap[i] += value;
    				pollDown(i);
    				return;
    			}
    		}
    	}
    
    	public void increasePriority(int key, int value) {
    		for (int i = 1; i <= heapSize; i++) {
    			if (heap[i] == key) {
    				heap[i] -= value;
    				pushUp(i);
    				return;
    			}
    		}
    	}
    
    	public void deleteInnode(int key) {
    		for (int i = 1; i <= heapSize; i++) {
    			if (heap[i] == key) {
    				heap[i] = heap[heapSize];
    				heapSize--;
    				pollDown(i);
    				return;
    			}
    		}
    	}
    }
    


    展开全文
  • 两种方法建时间复杂度

    千次阅读 2018-09-24 14:46:35
    Floyd建算法(自下而上下滤)建立规模为n的完全二叉的时间复杂度为:O(n) 一般的暴力建算法(自上而下下滤)时间复杂度为:O(nlogn)

    Floyd建堆算法(自下而上下滤)建立规模为n的完全二叉堆的时间复杂度为:O(n)

    一般的暴力建堆算法(自上而下上滤)时间复杂度为:O(nlogn)

    展开全文
  • 当把一个新的结点插入中时,需要对结点进行调整,以保证插入结点后的依然是大根。 其中h = log2(n+1)-1,第k层结点个数为2k个(当然最后一层结点个数可能小于2h)。第k层的一个结点插入之...
  • 大小详解&C++实现&复杂度分析

    千次阅读 2018-07-13 21:53:08
    大小堆介绍部分转载自:二叉堆之图文解析 二叉堆的删除、复杂度分析和代码是自己写的~ 堆和二叉堆的介绍 堆的定义 堆(heap),这里所说的堆...将任意节点不大于其子节点的堆叫做最小堆或小根堆,而将任意节点不...
  • 构建的时间复杂度

    万次阅读 多人点赞 2017-02-26 19:11:41
    大顶堆、小顶堆是一种很常用的数据结构,例如常见的排序和topk算法,在很多应用场景中,我们经常会关注算法时间复杂度和空间复杂度,众所周知构建的时间复杂度是o(n),那么为什么是o(n)?本文主要跟大家讨论下这...
  • 二叉操作时间复杂度分析

    千次阅读 2018-12-30 22:34:47
    二叉和二项式、斐波拉契都是用于实现优先队列的高级数据结构,以不同实现的优先队列会有不同的时间复杂度。 问题引入 在实际应用中,我们经常会遇到在最多由n个数组成的动态集合S SS上得到这个集合里面的...
  • 可以通过siftdown或者siftup建立二叉。 siftdown: 如果节点小于其最大的子节点,将二者进行交换,直到节点大于或等于所有子节点。整个过程节点向下调整。 siftup: 如果节点大于其父节点,将二者交换,直到节点...
  • 1、的概念 数据集合如果有序,将为各种操作带来遍历。但是有些应用并不要求数据全部有序,或者在操作开始前就完全有序。在许多应用中,通常需要先收集一部分数据,从中挑选出具有最小或者最大关键码的记录开始...
  • title: TopK问题用快排和排的复杂度分别是多少? categories: 算法 tags: TopK 关于TopK问题 TopK问题就是在一数据里面找到前 K 大(当然也可以是前 K 小)的数 常规方法,完全排序 先完全排序后取topK,这种...
  • 最大堆和最小堆

    2016-03-14 20:21:49
    最大堆和最小堆是二叉堆的两种形式。 最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。 最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。 ...
  • 堆排序算法是建立在二叉树的堆结构上的,通过交换堆(一维数组)中的元素,并进行上浮或下沉函数运算实现多次调整 堆排序算法的复杂度低,和快速排序属于相同速度级别的一种快速的排序算法 下面以最小堆
  • 之前看了下排序,此处的感觉和我理解的不是一个东西。此文力图探讨以下问题: 1.排序中“”的含义 2.排序算法的实现 3.算法的复杂度分析 4.排序蕴含的原理
  • 【解题思路】:我们知道如果一个二叉树满足的特性,那么顶元素则一定是整个中最大或最小的元素(这取决于大或小),那如果我们需要将一组数据进行升序排序,那么我们将这组元素拿来创建一个大顶元素...
  • 2-6 设最小堆(小根堆)的层序遍历结果为 {8, 38, 25, 58, 52, 82, 70, ...用线性时间复杂度的算法将该堆调整为最大堆(大根堆),然后连续执行两次删除最大元素操作(DeleteMax)。则该树的中序遍历结果为: ...
  • 最大堆最小堆操作——python

    千次阅读 2019-05-06 16:12:21
    刚讲完的一系列基本内容,把涉及的知识点整理下,看课本81-88页自行对照复习。 heap,通常是一个可以被看做一棵树的数组对象。 的性质:(1)是轶可完全二叉树;(2)某个节点的值总是大于或小于子节点 相关...
  • 最大最小堆整理 & heapq最小最大堆

    千次阅读 2018-11-27 20:42:24
    关于排序的视频演示: https://www.bilibili.com/video/av18980178/ 对于一个数组,可以使用min()和max()来求最大最小值而不是使用,但是根据python的wiki:https://wiki.python.org/moi...
  • 一文搞懂实现优先队列!
  • 最大堆最小堆的实现(C语言)

    千次阅读 2019-08-05 16:30:33
    是特殊的队列,从中取元素是按照元素的优先级大小,而不是元素进入队列的先后顺序。因此,也通常被称为“优先队列”。 的最常用结构是用二叉树表示,不特指的话,他是一棵完全二叉树。因此通常不必用指针,...
  • 是一种完全二叉树,现实中通常使用顺序结构的数组来存储,此处的是一种数据结构(完全二叉树),而不是虚拟进程空间中的那个(是操作系统用来管理内存的一个区域分段 )
  • 千次阅读 多人点赞 2020-10-20 11:11:19
    what ? why ? when ? how ? why 为什么要用? what 什么是有什么特点? how 如何操作(建立、插入、删除、查找)? when 什么是是特殊的“队列”,从中取出元素是...
  • 红黑树 vs 最小堆

    2020-02-01 15:10:43
    不谈内存,从算法上来讲 红黑树插入是最坏情况要比较2logN次(最高的高度)外加不超过两次旋转,最小堆最坏情况是logN次 ...红黑树的最坏情况在旋转中不断调整变化,插入性能比最小堆差,但删除最小性能却比最...
  • 最小堆以及最小优先队列的实现什么是最小堆构建最小堆MIN_HEAPITY的实现MAX_HEAPIFY的时间复杂度分析BUILD_MIN_HEAP的实现建最小堆的时间复杂度分析 什么是最小堆 最小堆从逻辑上可以理解为一个完全二叉树(如图a所...
  • [数据结构]最小堆的类模板实现

    千次阅读 2015-07-30 18:06:26
    它的特点是父节点的值大于(小于)两个子节点的值(分别称为最大堆和最小堆)。它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等。1、根结点若有子树,则子树一定也是堆。2、根结点一定大于(或...
  • 一:建 第一种情况:时间复杂度O(logn) ...b)若比父亲大则不需要处理,调整完成,整个树已经是小。 //向下调整算法 void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void AdjustDown
  • 最小堆 最小堆的定义 1、是一棵满二叉树 2、子树也是一棵满二叉树 3、左右节点的值都比当前节点的大 从定义可知,根节点是树中的最小值, 最小堆一般用链表存储,父子节点的关系,用纯数学的关系表示为:假设当前...
  • 建议读者先去下载《啊哈算法》看大概在P182页的堆,什么是最小堆? ps:如果想进来学习什么是堆的童鞋们,你们不需要再继续往下面阅读啦,对你们有意义的是第一行哦~随后我将此本算法书会长传到csdn上哦~ 而已经...
  • 时间复杂度和空间复杂度 时间复杂度:建:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*logn); 五、冒泡排序 打个小guang告,搜索拼duoduo店铺:Boush杂货铺 物美价廉,你值得拥有 1.基本思路 一次冒泡...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,767
精华内容 13,906
关键字:

最小堆调整复杂度