堆排序

作者: GallenZhang | 来源:发表于2019-03-06 17:21 被阅读0次

什么是堆?

“堆”是一种常用的数据结构,也是一种特殊的树。我们来看看,到底什么样的树才是堆。堆有如下两点要求,满足这两点要求的,就是一个堆。

1.堆是一个完全二叉树
2.堆中的每个节点值都必须大于等于(或小于等于)其子树每个节点的值。

第一点,堆是完全二叉树。那就意味除了树的最后一层,其他层节点个数都是满的,最后一层的节点都靠左排列。
第二点,换种说法就是,堆中的每个节点都大于等于(或小于等于)其左右节点的值。

对于每个节点值都大于等于子树每个节点的值的堆,称之为“大顶堆”。对于每个节点值都小于等于子树中每个节点值的堆,称之为“小顶堆”。“大顶堆”的第一个元素为最大值,“小顶堆”的第一个元素为最小值。

堆有哪些操作?

完全二叉树比较适合用数组来存储,这样比较节省存储空间。因为不需要存储左右子节点的指针,只要通过数组的下标,就可以很方便的找到一个节点的左右子节点和父节点。

下面是一个大顶堆的例子,数组下标从1开始。


从图中可以看出,对于任意一个下标为i的节点,这个节点的左子节点是下标为 i*2 的节点,右子节点是下标为 i * 2 + 1的节点,父节点是 i / 2 的节点。

知道了如何存储一个堆后,接着看看堆有哪些操作。堆有两个非常核心的操作:往堆中插入一个元素、删除堆顶元素。

1.往堆中插入一个元素
往堆中插入一个元素后,堆结构需要继续满足堆的两个特性。将新元素放到堆最后,如果不符合堆的特性,那就需要进行调整重新满足堆的特性,这个调整的过程叫做“堆化”。

堆化有两种,“从上往下”和“从下往上”。下面使用“从下往上”的方式来实现往堆中插入元素。

“从下往上”这种堆化方式非常简单,新插入的节点与父节点比较大小。如果不满足子节点小于等于父节点,那么就互换两个节点。重复这个过程,直到父子节点之间满足这种关系为止。


根据上面的思路,插入元素的代码可以结合着图示一起看。

  public class Heap{
    private int[] arr;  //二叉树数组
    private int count;  //堆中已经存储的数据个数
    public Heap(int capacity){
      arr = new int[capacity + 1];
      n = capacity;
      count = 0;
    }

  public void insert(int data){
       if(count + 1 >= arr.length){
            throw new IllegalArgumentException();
       }
       count++;
       arr[count] = data;
       int pos = count;
       while (pos / 2 > 0 && arr[pos / 2] < arr[pos]){
            swap(pos,pos / 2);
            pos = pos / 2;
       }
   }
}

2.删除堆顶元素
删除堆顶元素后,同样也需要保证堆能够满足那两个特性。删除堆顶元素后,我们可以把堆中最后一个元素放到堆顶。然后利用父子节点对比方法,对于不满足父子节点大小关系的节点,互换两个节点,重复进行这个过程,直到父子节点之间满足二叉堆的特性为止。这里使用的是“从上往下”的方法进行堆化。


根据上面的思路,删除堆顶元素的代码可以结合着图示一起看。

public void removeTop(){
    if(count == 0 ){
        retun;
    }
    a[1] = arr[count];
    count--;
    int  pos = 1;
    int maxPos = 1;
    while(true){
        if(pos * 2 <= count && arr[pos * 2] > arr[pos]){
            maxPos = pos * 2;
        }
        if(pos * 2 + 1 <= count && arr[pos * 2 + 1] > arr[pos]){
            maxPos = pos * 2 + 1;
        }
        if(maxPos == pos){
            break;
        }
        swap(arr,pos,maxPos);
        pos = maxPos;
    }
}

一颗包含n个节点的完全二叉树,树的高度不会超过\log_2n。堆化的过程是顺着节点的路径进行比较交换,所以堆化的时间复杂度跟树的高度成正比,也就是O(log n)。因为插入和删除都是做的堆化操作,所以他们的时间复杂度都是O(log n)。

堆排序怎么实现?

我们可以借助堆这种数据结构实现的排序算法,就叫堆排序。这种排序算法的时间复杂度很长稳定,是O(n log n)。堆排序的过程可以分为两个步骤,构建堆和排序。

1.构建堆
将待排序的数据构建成堆,构建堆有两种思路。

第一种就是借助前面说的,在堆中插入一个元素。我们可以假设最开始堆中只包含一个下标为1的数据。然后我们调用插入操作,将下标从2到n的数据依次插入到堆中。这样我们就将包含n个数据的数组,组织成了堆。

第二种实现,和第一种思路相反。第一种建堆处理过程是从前往后处理数组数据,每个数据插入堆中,都是从下往上堆化。而第二种实现思路是从后往前处理数组,并且每个数据都是从上往下堆化。

可以参照下面的例子,叶子节点堆化只能和自己比较,所以我们直接从第一个非叶子节点开始,依次堆化就可以。


对照着图示,将建堆的过程翻译成代码。

    /**
     * 构造堆
     */
    private void buildHeap(){
        for(int i = count / 2; i>0; i--){
            downAdjust(i,count);
        }
    }

    /**
     * "从上往下"调整
     * @param pos:下沉节点下标
     * @param n:堆有效大小
     */
    private void downAdjust(int pos,int n){
        int maxPos = pos;
        while (true){
            if(pos * 2 <= n && arr[pos * 2] > arr[pos]){
                maxPos = pos * 2;
            }
            if(pos * 2 + 1 <= n && arr[pos * 2 + 1] > arr[maxPos]){
                maxPos = pos * 2 + 1;
            }

            if(maxPos == pos){
                break;
            }
            swap(pos,maxPos);
            pos = maxPos;
        }
    }

2.排序
经过建堆这个步骤后,数组就是一个标准的大顶堆了。数组中第一个元素是堆顶,也是数组中最大的元素。我们把它和最后一个元素交换,那么最大元素就放到下标为count的位置了。

这个过程类似于“删除堆顶元素”,当堆顶元素删除之后,我们把最后一个元素放到堆顶,然后通过“从上往下”方式堆化,将剩下count - 1个元素重新构建成堆。堆化完成后,再取堆顶元素放到下标是 count - 1位置,一直重复这个过程,直到堆中只剩下下标为1的一个元素,完成排序。


将上面的排序过程,翻译成排序代码。

    /**
     * 堆排序
     */
    public void sort(){
        int n = count;
        for (int i = count; i > 1 ; i--){
            swap(1,i);
            downAdjust(1,--n);
        }
    }

时间复杂度分析

在整个堆排序的过程中,需要极少的临时存储空间。堆排序包括建堆和排序两个操作,构建堆过程的时间复杂度是O(n),排序过程的时间复杂度是O(n log n),所以堆排序整体的时间复杂度是O(n log n)。

GitHub 代码地址: 二叉堆

相关文章

  • 堆排序

    目录 1.堆排序介绍 2.堆排序图文说明 3.堆排序的时间复杂度和稳定性 4.堆排序实现 堆排序介绍 堆排序(He...

  • 堆排序---基础篇

    本文主要介绍堆排序的一些基本过程和分析。 大纲 堆排序简介 堆排序代码实现 1. 堆排序简介 1.1 堆排序的存储...

  • 堆和堆排序

    最小K个数 堆排序 堆排序

  • JS实现堆排序

    原理 堆排序原理 实现 说明 堆排序对大文件很有效 堆排序是不稳定排序

  • iOS算法总结-堆排序

    iOS算法总结-堆排序 iOS算法总结-堆排序

  • 堆排序

    转载:图解排序算法(三)之堆排序 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选...

  • 排序

    原创 堆排序: 使用visit数组从本质出发获取大顶堆排序。

  • 堆排序

    堆排序

  • C++基础入门之模板堆排序(上):模板上的list的创造与操作

    整段源码链接C++的模板元堆排序 要点 组建数据结构list 组建对list的各种基本操作 堆排序中组建堆排序个个...

  • 3.2-选择排序-堆排序

    参考链接 选择排序:堆排序(Heap Sort) 白话经典算法系列之七 堆与堆排序 堆排序与快速排序,归并排序一样...

网友评论

      本文标题:堆排序

      本文链接:https://www.haomeiwen.com/subject/dixzuqtx.html