精华内容
下载资源
问答
  • 最小堆怎么建立

    千次阅读 2015-09-17 17:47:50
    解决方式是,用一个100个容量的最小堆, 这100个数总数目前已知的最大的100个,而且 堆顶是小的, 在继续遍历时候,只和堆定比较, 如果这个数,比堆顶的大, 就把这个数加入 这个堆。 当遍历完成后,这个最小堆...

    有一个面试题,100w个数中找到最大的100个数。
    解决方式是,用一个100个容量的最小堆, 这100个数总数目前已知的最大的100个,而且
    堆顶是小的, 在继续遍历时候,只和堆定比较, 如果这个数,比堆顶的大, 就把这个数加入
    这个堆。
    当遍历完成后,这个最小堆中的数,就是最大的100个数了。

    当理解了这个, 我还有一个疑惑, 什么是最小堆。

    http://blog.csdn.net/genios/article/details/8157031

    学习了这个篇帖子。 受益匪浅。 文章写的很好, 一开始很难理解,跟着模拟了一下,

    关键是要自己模拟程序,去移动一下 这个树,才理解。

    
    typedef struct heap HEAP;
    struct heap {
         int arr[127];
         int size;
    };
    
    void insert(HEAP *h,int n){
           int sz = h->size++;
           printf("%d --- %d\n",sz,n);
           while(sz>0){
                if(n < h->arr[(sz-1)/2]){//若改成 > 则为大根堆
                    h->arr[sz] = h->arr[(sz-1)/2];
                    sz = (sz-1)/2;
                }else{
                    h->arr[sz] = n;
                    return;
                }
           }
           h->arr[0] = n;
    }
    
    void delete(HEAP *h){
           h->size--;
           h->arr[0] = h->arr[h->size];
           h->arr[h->size] = 0;
           int i = 1,cv = h->arr[0],tmp;
           while(i < h->size){
                   if(i < h->size-1 && h->arr[i] > h->arr[i+1])
                          i++;
                   if(h->arr[i] < cv){
                          h->arr[(i-1)/2] = h->arr[i];
                          h->arr[i] = cv;
                          i = i*2 + 1;
                   }else{
                          return;
                   }
           }
    }

    下面这个是我自己改的,上面的是 wikipedia上copy的

    #include <iostream>
    
    typedef struct heap HEAP;
    
    struct heap
    {
        int arr[100];
        int size;
    };
    
    
    //将数字num 插入 最小堆
    //游标 比 位置 小一
    void insert(HEAP *h, int num)
    {
    
        int sz = h->size;
        h->size++;
    
        while( sz >0 ){
            if(num > h->arr[(sz-1)/2]){
                h->arr[sz] = num;
                return;
            }else{
                h->arr[sz] = h->arr[(sz-1)/2]; 
                sz = (sz-1)/2;
            }   
        }   
    
        h->arr[0] = num;
    
    }
    
    
    
    
    void c_delete(HEAP *h) 
    {
        h->size--;
        h->arr[0] = h->arr[h->size];
        h->arr[h->size] = 0;
    
        int i=1;
        int cv = h->arr[0];
    
        while(i<h->size){
            if(cv < h->arr[i] && cv < h->arr[i+1]){
                return ;
            }   
    
            if(h->arr[i] > h->arr[i+1])
                i++;
            else{
                h->arr[(i-1)/2] = h->arr[i];
                h->arr[i] = cv;
                i = i*2 +1;
            }
        }
    }
    
    
    int main()
    {
        return 0;
    }
    
    
    展开全文
  • 在树这个数据结构定义的时候是递归定义的所以也就满足,一个树中子数的更节点是最大或者最小(取决与建立还是小)。 建立 建立过程是一个进行比较的过程,也就是说,每次插入一个元素,就需要对...

    堆的实现

    堆的本质是一二叉树,并且是一颗完全二叉树。

    堆分为大堆和小堆,大堆就是在堆顶的元素的值是这个完全二叉树中的最大值,小堆刚好相反,是最小值。在树这个数据结构定义的时候是递归定义的所以也就满足,一个树中子数的更节点是最大或者最小(取决与建立大堆还是小堆)。

    堆的建立

    堆的建立过程是一个进行比较的过程,也就是说,每次插入一个元素,就需要对堆进行调整,怎么调整?当然在插入的时候,我们就已经确定需要建立大堆还是小堆,所以我们在插入的时候,每次都插入到堆的尾部,应为堆是一个完全二叉树,所以,我们插入到尾部后就需要和父节点的值进行比较,再进行调换,如果发现不用调换就说明插入完成。

    堆的建立是基于一个顺序表的数据。

    具体是的实现:

    void Swap(int *a, int *b)
    {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    // 调整堆
    void AdjustUp(int arr[], size_t size, size_t index)
    {
        if (arr == NULL)
        {
            return;
        }
        size_t child = index;
        size_t parent = (size - 1 - 1) / 2;
        while (child > 0)
        {
            if (arr[child] < arr[parent])
            {
                Swap(&arr[child], &arr[parent]);
            }
            // 因为是尾部插入然后上移,当上移到parent < child时候,
            // 就需要停止,不然会继续向上判断。
            else 
            {
                break;
            }
            child = parent; 
            parent = (child-1) / 2; 
        }
    }
    
    void CreateHeap(int arr[], size_t size)
    {
        for (int i = 0; i < size; ++i)
        {
            // 在堆尾部插入,每次堆增加1
            AdjustUp(arr, i,i);
        }
    }

    取堆顶元素

    我们建堆的目的一般都是为了排序或者取最大或者最小的数值,那么就需要取堆的顶部元素。我们来实现取堆顶元素

    // 因为我们用到是c语言,所以我们用了输出型参数value
    int HeapFindRoot(int arr[], int *value)
    {
        if (arr == NULL || value == NULL)
        {
            // 取失败
            return 0;
        }
        *value = arr[0];
        return 1;
    }
    

    取完堆顶元素,那么就要删除,在堆排序中,正是删除堆顶元素,然后在对堆进行调整就会得到新的堆顶元素。
    代码:

    删除堆顶元素

    // 下沉
    void AdjustDown(HeapType arr[],size_t size, size_t index)
    {
        if (arr == NULL)
        {
            return;
        }
        size_t lchild = index * 2 + 1;
        while (lchild < size)
        {
            // 如果是右孩子小于左孩子,那么把下标为右孩子赋给左孩子下标。
            if ((lchild + 1 < size) && cmp(arr[lchild + 1], 
            \arr[lchild]))
            {
                lchild = lchild + 1;
            }
            // 把孩子中小的一个与父节点值比较,如果父值大,
            //子小,那么交换。否则跳出循环。
            if (cmp(arr[lchild], arr[index]))
            {
                Swap(&arr[lchild], &arr[index]);
            }
            else
            {
                break;
            }
            // 更新index和孩子节点下标。
            index = lchild;
            lchild = index * 2 + 1;
        }
    }
    
    // 删除堆顶元素。
    void HeapErase(int arr[],size_t size)
    {
        if (arr == NULL)
        {
            return;
        }
        Swap(&arr[0], &arr[size-1]);
        --size;
        size_t index = 0;
        AdjustDown(arr, size, index);
    }

    以上就是堆数据结构都是用int型。我们在实际中也可以是一个结构体,也可以是进程,进程的优先调度算法就是用一个堆的数据结构来实现。

    堆排序

    堆排序是一种时间复杂度为O(nlogn)算法。空间复杂度为O(n)的算法。

    下沉
    void AdjustDown(HeapType arr[],size_t size, size_t index)
    {
        if (arr == NULL)
        {
            return;
        }
        size_t lchild = index * 2 + 1;
        while (lchild < size)
        {
            // 如果是右孩子小于左孩子,那么把下标为右孩子赋给左孩子下标。
            if ((lchild + 1 < size) && cmp(arr[lchild + 1], 
            \arr[lchild]))
            {
                lchild = lchild + 1;
            }
            // 把孩子中小的一个与父节点值比较,如果父值大,
            //子小,那么交换。否则跳出循环。
            if (cmp(arr[lchild], arr[index]))
            {
                Swap(&arr[lchild], &arr[index]);
            }
            else
            {
                break;
            }
            // 更新index和孩子节点下标。
            index = lchild;
            lchild = index * 2 + 1;
        }
    }
    
    // 时间复杂度为O(N * LogN)
    void HeapSort1(HeapType arr[], size_t size)
    {
        if (arr == NULL || size <= 1)
        {
            return;
        }
        // 先减一是计算时是从0开始,第二个是child推导parent公式
        size_t begen = (size - 1 - 1)/2;
        // 这里采用下沉建树
        for (; begen > 0; --begen)
        {
            AdjustDown(arr, size, begen);
        }
        AdjustDown(arr, size, 0); // 这是处理0这种情况
        size_t heap_size = size;
        while (heap_size > 0)
        {
            Swap(&arr[0], &arr[heap_size - 1]);
            --heap_size;
            AdjustDown(arr, heap_size, 0);
        }
    }
    展开全文
  • 排序(代码思路)

    2020-02-16 12:10:37
    假设你已经学建立最大堆或者最小堆 那么怎么利用最大堆来进行堆排序呢? 1:因为堆顶元素一定是最大值,然后将其输出 2:吧堆顶元素与堆的最后一个元素交换, 删除堆的最后一个元素, 将顶元素进行下移操作,这样又...

    参考资料1,写的挺不错
    还有这个

    假设你已经学建立最大堆或者最小堆

    那么怎么利用最大堆来进行堆排序呢?
    1:因为堆顶元素一定是最大值,然后将其输出
    2:吧堆顶元素与堆的最后一个元素交换,
    删除堆的最后一个元素,
    将顶元素进行下移操作,这样又可以保证堆顶元素是最大值
    3:重复操作1和2直到结束

    #include<iostream>
    #include<algorithm>
    #include<random>
    #include<time.h>
    using namespace std;
    int a[100];
    int h[100];
    int maxn;
    
    void heapDown(int k) {
    	while ( (k=2*k)<= maxn ) {
    		if (k + 1 <= maxn && h[k + 1] > h[k])
    			k++;
    		if(h[k]>h[k/2] ) 
    			swap(h[k], h[k / 2]);
    		else break;
    	}
    }
    void heapUp(int k) {
    	while (k > 1) {
    		if (h[k] > h[k / 2])
    			swap(h[k], h[k / 2]),
    			k /= 2;
    		else break;
    	}
    }
    void insertHeap(int k) {
    	h[k] = a[k];
    	heapUp(k);
    }
    void makeHeap() {
    	for (int i = 1;i <= maxn;i++) {
    		insertHeap(i);
    	}
    }
    void heapSort() {
    	while (maxn) {
    		cout << h[1] << " ";
    		swap(h[1], h[maxn]);
    		maxn--;
    		heapDown(1);
    	}
    }
    int main()
    {
    	srand((unsigned)time(NULL));
    	cin >> maxn;
    	int n = maxn;
    	for (int i = 1;i <= maxn;i++) {
    		a[i] = rand() % 10000;
    		makeHeap();
    	}
    	heapSort();
    
    }
    
    展开全文
  • 排序算法-排序

    千次阅读 2015-06-22 21:29:11
    堆排序算法是建立在堆这种数据结构的基础上,其实堆听着很高端,其实很简单,就是一个二叉树,但是又特殊条件,就是其父节点比孩子节点都大(或都小)的堆称为最大堆(最小堆),瞬间感觉很简单了,最简单的保存方法...

    堆排序算法是建立在堆这种数据结构的基础上,其实堆听着很高端,其实很简单,就是一个二叉树,但是又特殊条件,就是其父节点比孩子节点都大(或都小)的堆称为最大堆(最小堆),瞬间感觉很简单了,最简单的保存方法就是直接用数组来保存。
    给出一组数,我们要使用堆排序,首先需要建堆,但是这一组数首先肯定是不满足上面堆的性质的,所以我们需要调整,让他满足堆得性质,变成一个堆,怎么调整呢?拿最大堆来说,就是对于一个节点,我们判断其孩子是否有比父亲节点大的,有的话,交换这两个值,这样父亲就比孩子都大了,当然交换完了之后可能以这个孩子为根节点的子树又不满足对性质了,继续交换直到都满足,为了减少交换的次数,我们可以从离叶子节点最近的节点开始交换,一层一层直到根节点。
    比如这样一组数a[]={16,7,3,20,17,8},我们建堆
    这里写图片描述
    然后依次调整
    这里写图片描述这里写图片描述这里写图片描述这里写图片描述
    这样一个堆就建立起来了。剩下的事情就很简单了
    有了堆之后我们很容易发现堆有一个很美好的性质,就是根节点的值闭锁所有的值都大(小),那么我们第 i 次选择根节点,放入数组第【n-i+1】,然后把第【n-i+1】的值放到根节点,调整堆,经过n次之后就是一个有序的了。过程如下1
    这里写图片描述这里写图片描述这里写图片描述这里写图片描述这里写图片描述这里写图片描述这里写图片描述这里写图片描述这里写图片描述这里写图片描述
    (图片非原创,有版权问题请联系我删除)
    堆排序被归类到选择排序里面,因为其思想和选择排序的思想是一样的,从剩下的数组里面选择一个最大的(最小的),放到排好序的位置,然后继续选择,只是选择排序选择一次的复杂度是O(n),这里选择是O(1),但是选择完了需要调整,调整的复杂度是log(n),所以总的复杂度是O(n*logn)。
    其实堆的另一个很常用的用法就是优先队列,所以大家可以看出来优先队列的复杂度了,每插入一个元素是O(logn),取出时O(1),这样大家就可以自己实现优先队列了

    代码:

    #include <iostream>
    #include <cstdio>
    #include <vector>
    using namespace std;
    const int N = 1001000;
    int a[N];
    
    void Balance(int x,int n)
    {
        int l = x+x;
        int r = x+x+1;
        int mid = x;
        if(l<n && a[l]>a[mid])
            mid = l;
        if(r<n && a[r]>a[mid])
            mid = r;
        if(x!=mid)
        {
            swap(a[x],a[mid]);
            Balance(mid,n);
        }
    }
    
    void Heap_Sort(int n)
    {
        for(int i=n/2-1;i>=0;i--)  //首先调整堆
            Balance(i,n);
        for(int i=n-1;i>=0;i--)
        {
            swap(a[i],a[0]);
            Balance(0,i);
        }
    }
    
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            Heap_Sort(n);
            for(int i=0;i<n;i++)
                printf("%d ",a[i]);
            puts("");
        }
        return 0;
    }
    
    展开全文
  • 最小生成树解析

    2020-06-25 22:38:35
    实际问题:我们要在n个城市中建立一个通信网络,则连通这n个城市需要布置n-1一条通信线路,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网? 二、普里姆算法—Prim算法(适合稠密图) 用优化后时间...
  •    堆排序属于选择排序类别,其算法步骤是:1、从无序序列建立最大堆(升序就构造最大堆)或者最小堆(降序就构造最小堆)2、利用构建的堆进行排序。    堆排序的平均时间复杂度和最坏时间复杂度均为在 O(nlogn...
  • 数据结构之小根

    2021-04-27 17:23:38
    因此顶的关键码是最小的,下面介绍小根堆怎么构建以及它的自顶 向下筛选法和自底向上算法,大根可以类似建立 1.自顶向下调整 先贴上我的小根的结构define #include<stdio.h> #include<stdlib.h> ...
  • 关于排序的一点总结

    千次阅读 2012-10-20 08:28:07
    这个排序看了很久都没有...所以在建立完大根(小根)后父节点始终是最大的(小根就是最小的),这里的思想和冒泡有点类似。 2. 初始化完了之后怎么做? 后面我才知道这个要反着来,当建立大根的时候A[0]是整
  • 思路:建立map用来存放每个数出现的频率,这一步大家都能想到,关键是怎么从map中读出前k个高频元素;这个时候我们应该想到使用优先队列;这边有两种方式,一种是使用默认的最小堆然后设定堆的大小为k;另一种方式是...
  • 先回顾一下哈夫曼树 huffman树即最优二叉树,是加权路径长度最短的二叉树。哈夫曼树的树使用贪心算法。...这里我们就可以建立一个小,每次找出最小的时候只需要向上调整就行了。 那么文件哈夫曼树怎么实现
  • 按照估价函数建立小根 每次取出最小的那个继续更新 每次更新到终点cnt++直道cft=k为止 那估价函数怎么弄呢? 其实就是终点到它的距离+已经走了的距离 所以其实很简单啊?? 可能需要多看几题了解一下 转载于...
  • 首先想,这里有一物品,你可以选择取用或者不取,每种有一定的收益,支付一定的代价,那么就决定是你了!背包!(抱歉不是dp,OJ会等你枚举个2n 次?) 权衡奖金与代价,这两者是有我没他的,怎么去处理呢? ...
  • 它是在几个项目捐助基础上建立起来的(nWidgets, Burstlib, f(m)),这也是为什么叫它a unified toolkit的原因。Dojo的目标是解决开发DHTML应用程序遇到的那些、长期存在、历史问题,以及DHTML 跨浏览器问题。 •Dojo...
  • 大话数据结构

    2018-12-14 16:02:18
    正所谓“巧妇难为无米之炊”,再强大的计算机,也要有“米”下锅才可以干活,否则就是一破铜烂铁。这个“米”就是数据。 1.4.1数据 5 1.4.2数据元素 5 1.4.3数据项 6 1.4.4数据对象 6 1.4.5数据结构 6 1.5...
  • java 面试题 总结

    2009-09-16 08:45:34
    是栈的一个组成元素 19、forward 和redirect的区别 forward是服务器请求资源,服务器直接访问目标地址的URL,把那个URL的响应内容读取过来,然后把这些内容再发给浏览器,浏览器根本不知道服务器发送的内容是从...
  • 提供了实现heap.Interface接口的任何类型的操作 lsit 实现了一个双链表 ring 实现了对循环链表的操作 crypto aes 实现了AES加密(以前的Rijndael) cipher 实现了标准的密码块模式,该模式可包装进低级...
  • 第三,实践类的操作系统书籍还是太少了,以至于你要想看看别人是怎么做的,除了读以《操作系统:设计与实现》为代表的极少数书籍之外,就是一头扎进源代码中,而结果有时相当令人气馁。我自己也气馁过,所以我在第二...
  • 第三,实践类的操作系统书籍还是太少了,以至于你要想看看别人是怎么做的,除了读以《操作系统:设计与实现》为代表的极少数书籍之外,就是一头扎进源代码中,而结果有时相当令人气馁。我自己也气馁过,所以我在第二...
  • 2.5.8 以最小的磁盘开销跟踪净数据更改 93 第3章 事务、锁定、阻塞和死锁 100 3.1 事务控制 100 3.1.1 使用显式事务 101 3.1.2 使用DBCC OPENTRAN显示最早的活动事务 104 3.1.3 通过会话查询事务信息 104...
  • ExtAspNet_v2.3.2_dll

    2010-09-29 14:37:08
    -修正弹出对话框的宽度计算错误(会保持最小的状态)。 -增加新的皮肤Gray。 -为示例工程添加改变语言和皮肤的下拉列表。 -为PageContext增加静态函数Refresh,在切换语言和皮肤时使用。 +2009-12-01 v2.1.7...
  • -修正弹出对话框的宽度计算错误(会保持最小的状态)。 -增加新的皮肤Gray。 -为示例工程添加改变语言和皮肤的下拉列表。 -为PageContext增加静态函数Refresh,在切换语言和皮肤时使用。 +2009-12-01 v2.1.7...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

怎么建立最小堆