数据结构与算法-堆以及堆排序

Posted on | Edited on | In ,

堆的特点以及实现

堆的定义：任意一个节点都大于（小于）他们的子节点，堆顶是最大（小）的元素，如果堆顶是最大的元素成为大顶堆，如果堆顶是最小的元素成为小顶堆

堆是完全二叉树，底层实现是通过数组实现。他们之间的关系如下：

  • 下标为i的节点leftNode的下标是2i+1，rightNode是2(i+1)
  • 下标为i的节点他的父节点是(i-1)/2

堆的几种操作原理

插入–自下而上的堆化

时间复杂度O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void insert(int value) {
    if (count == capacity) {
        System.out.println("堆已经满了");
        return;
    }

    array[count] = value;
    int i = count;
    count++;
    //插入到堆最后一个节点，然后开始迭代，判断如果节点如果大于父节点交换俩个节点，这时候堆顶就是最大的数据
    while (i > 0) {
        int pIdx=(i - 1) / 2;
        if (array[i] > array[pIdx]) {
          swap(array,i,pIdx);
        }else{
          break;
        }
        i=pIdx;
    }
}

删除–自上而下的堆化

时间复杂度是O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//删除堆顶
public void delTop() {
    //删空了
    if (count == 0) {
        return;
    }
    
    //为了防止空洞直接，将最后一位数据和堆顶交换，删除最后一位数据，然后将新的堆顶自上而下的堆化
    array[0] = array[count - 1];
    array[count - 1] = 0;
    count--;
    heapify(array, count - 1, 0);
}

 //自上而下的堆化操作。遍历在自己的子节点中发现有比自己大的值，就和自己替换比较
private static void heapify(int[] a, int heapCapicity, int i) {
    while (true) {
        int top = i;
        //如果当前元素小于左子节点，将左子节点和当前节点值交换。
        if (2 * i + 1 <= heapCapicity && a[top] < a[2 * i + 1]) {
            top = 2 * i + 1;
        }
        //如果当前元素小于右子节点，将右子节点和当前节点值交换。
        if (2 * (i + 1) <= heapCapicity && a[top] < a[2 * (i + 1)]) {
            top = 2 * (i + 1);
        }

        //没变说明不需要交换直接跳出循环
        if (top == i) {
            break;
        }
        swap(a, top, i);
        i=top;
    }
}

堆排序的原理

大致分俩个步骤，升序为例建大顶堆，降序建小顶堆

  1. 建堆：整个数组的[0，n/2]是非叶子节点，对所有的非叶子节点进行自上而下的堆化操作。时间复杂度O(NlogN)
  2. 排序：因为堆顶元素是最大的，所以将堆顶和堆尾的元素交换，然后堆范围缩小1，再次交换堆顶，直到最后一位。时间复杂度O(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void buildHeap(int a[]) {
    //从非叶子节点开始建堆
    for (int i = a.length / 2-1; i >= 0; i--) {
        heapify(a, a.length , i);
    }
}


public static int[] sort(int a[]) {
    buildHeap(a);
    System.out.println("buildHeap:"+Arrays.toString(a));

    //开始交换，直到剩下最后一个元素为止
    int swapIdx = a.length - 1;
    while (swapIdx > 1) {//注意剩下2个元素时候交换完后跳出循环
        swap(a, 0, swapIdx);//堆顶（Max）和交换区的元素交换
        swapIdx--;//缩小交换区
        heapify(a,swapIdx,0);//找第二大的元素
    }
    return a;
}

时间复杂度o(nlogn)

堆排序的缺点

  1. 堆是个完全二叉树无法想数组顺序访问那样很好的利用cpucache
  2. 堆排序数据的逆序度高。

堆的使用

优先级队列

java的优先级队列PriorityQueue实际上底层的实现就是堆，维护一个小（大）顶堆，堆顶就是队列的第一个元素。

类似的实现还有高性能定时器：我们定时任务都在一个队列中，通常的做法是每隔一段时间轮询队列，这样如果任务列表很长或者计算资源不足时候不是很精确同时也会浪费计算资源。我们如果用堆来实现的话，维护一个小顶堆，堆顶是最先执行的任务，我们定时器取堆顶的任务计算和现在的时间差T如果T>0,线程就睡眠T时间，这样节省了资源，当小于等于0时候开始执行任务，同时从堆中移除。

topn问题

N个文件中取topN，比较坏的做法是，每个文件取一个放在数组中，然后从第一个文件中取出来循环和数组中的数据比较，如果发现大于数组中的值就放入数组。这样时间复杂度很高；用堆的思想，我们可以我们可以维护一个元素为N的小顶堆，依次取文件如果发现比小顶堆小就插入到小顶堆中。

一个静态的大文件中取topn，静态文件我们可以维护一个元素为N的小顶堆，方式同上；动态数据我们可以始终维护一个小顶堆。

求中位数

场景：比如运维中求中位数，90分位等的要求，即100份，前0份或者90份的样本数的大小。如：1，2，3，4，5，6。中的3，4都可以做中位数，一般取3

方法：我们可以把样本数分为俩部分，用俩个堆来维护，前n/2的数据放在大顶堆中，后面的数据放在小顶堆中，大顶堆的堆顶就是中位数。当有新的样本数据插入时候判断如果小于大顶堆就插入到大顶堆中，否则就插入小顶堆中。这时候可能破坏了平衡，那么我们可以将新插入的那个堆的堆顶元素置换到另一个堆中来保持平衡