大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

堆的性质是什么?怎么实现堆?-创新互联

堆的性质:

  • 堆在逻辑上是一棵完全二叉树
  • 堆是基于数组实现的,堆的所有元素都存储在数组中
  • 满足任意结点的值都大于其子树中结点的值的堆,称为大堆
  • 满足任意结点的值都小于其子树中结点的值的堆,称为小堆
  • 堆的基本作用是快速的在集合中找到最值

堆的实现(小堆为例):

  1. 堆的向下调整(siftDown):为了满足小堆的性质,即任意结点的值都小于其子树中结点的值,因此需要对指定结点进行向下调整,代码如下:

    创新互联建站服务项目包括翼城网站建设、翼城网站制作、翼城网页制作以及翼城网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,翼城网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到翼城省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
    //size是数组的大小,index是需要向下调整的元素的下标
    public void siftDown(int[] array, int size, int index) {
       int left = (index << 1) + 1;
       //堆是完全的二叉树,如果没有左节点,那么必定没有右节点,因此以左节点作为先决条件
       while(left < size) {
         //先假定最小的值时左节点的值
         //原因:进入循环左节点必定存在,然后再判断右节点是否存在,
         //不存在的话最小值肯定是左节点,如果存在的话,只有当右节点的值小于左节点时才会让最小值时右节点的值
         int min = left;
         int right = (index << 1) + 2;
    
         //只有右节点存在且小于左节点的值时才进入循环
         if(right < size && array[right] < array[left]) {
             min = right;
         }
    
         //如果两子节点中的最小值都大于他本身的值时,调整结束
         if(array[min] >= array[index]) {
           break;
         }
    
         //交换指定节点和其子节点中最小值的节点
         int tmp = array[index];
         array[index] = array[min];
         array[min] = tmp;
    
         //调整后下标是min的结点等待继续调整
         index = min;
         left = (index << 1) + 1;
       }
    }
  2. 构建堆(heapify):从最后一个非叶子结点开始向下调整直到根节点(下标为0的元素)后,表示任意结点都满足了小堆的性质,实现方式如下:
    //此处size是数组最后一个元素的下标
    public void heapify(int[] array, int size) {
       for (int i = (size - 1) >> 1; i >= 0; i--) {
         new SiftDown().siftDown(array, size, i);
       }
    }

    3.下述为PriorityQueue在构建堆时的源码:

    //其中size表示的是数组中元素的个数,因此和上面构建代码中的循环条件有所差别,但是本质表达的是一个意思
    private void heapify() {
       for (int i = (size >>> 1) - 1; i >= 0; i--)
         siftDown(i, (E) queue[i]);
    }

堆最常解决的问题:

  • TopK问题
  • 排序问题

堆的应用—优先级队列:

  • 提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
  • 优先级队列的实现方式有很多,但是最常见的是使用堆来构建
  • Java中的优先级队列就是通过构建堆来实现的

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


标题名称:堆的性质是什么?怎么实现堆?-创新互联
网站地址:http://dzwzjz.com/article/ceiecp.html
在线咨询
服务热线
服务热线:028-86922220
TOP