【42期】盘点那些必问的数据结构算法题之二叉堆

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 【42期】盘点那些必问的数据结构算法题之二叉堆

点击上方“Java面试题精选”,关注公众号

面试刷图,查缺补漏

号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。

0 概述

本文要描述的堆是二叉堆。二叉堆是一种数组对象,可以被视为一棵完全二叉树,树中每个结点和数组中存放该结点值的那个元素对应。树的每一层都是填满的,最后一层除外。二叉堆可以用于实现堆排序,优先级队列等。本文代码地址在 这里。

https://github.com/shishujuan/dsalg/tree/master/code/ds/heap

1 二叉堆定义

使用数组来实现二叉堆,二叉堆两个属性,其中 LENGTH(A) 表示数组 A 的长度,而 HEAP_SIZE(A) 则表示存放在A中的堆的元素个数,其中 LENGTH(A) = HEAP_SIZE(A),也就是说虽然 A[0,1,…N-1] 都可以包含有效值,但是 A[HEAP_SIZE(A)-1] 之后的元素不属于相应的堆。

二叉堆对应的树的根为 A[0],给定某个结点的下标 i ,可以很容易计算它的父亲结点和儿子结点。注意在后面的示例图中我们标注元素是从1开始计数的,而实现代码中是从0开始计数。


#define PARENT(i) ( i  0 ? (i-1)/2 : 0)
#define LEFT(i) (2 * i + 1)
#define RIGHT(i) (2 * i + 2)

注:堆对应的树每一层都是满的,所以一个高度为 h 的堆中,元素数目最多为 1+2+2^2+…2^h = 2^(h+1) - 1(满二叉树),元素数目最少为 1+2+…+2^(h-1) + 1 = 2^h。

由于元素数目 2^h = n = 2^(h+1) -1,所以 h = lgn h+1,因此 h = lgn 。即一个包含n个元素的二叉堆高度为 lgn 。

2 保持堆的性质

本文主要建立一个最大堆,最小堆原理类似。为了保持堆的性质,maxHeapify(int A[], int i) 函数让堆数组 A 在最大堆中下降,使得以 i 为根的子树成为最大堆。


void maxHeapify(int A[], int i, int heapSize)
{
    int l = LEFT(i);
    int r = RIGHT(i);

    int largest = i;

    if (l = heapSize-1 && A[l]  A[i]) {
        largest = l;
    }

    if (r = heapSize-1 && A[r]  A[largest]) {
        largest = r;
    }

    if (largest != i) { // 最大值不是i,则需要交换i和largest的元素,并递归调用maxHeapify。
        swapInt(A, i, largest);
        maxHeapify(A, largest, heapSize);
    }
}

在算法每一步里,从元素 A[i] 和 A[left] 以及 A[right] 中选出最大的,将其下标存在 largest 中。如果 A[i] 最大,则以 i 为根的子树已经是最大堆,程序结束。

否则,i 的某个子结点有最大元素,将 A[i] 与 A[largest] 交换,从而使i及其子女满足最大堆性质。此外,下标为 largest 的结点在交换后值变为 A[i],以该结点为根的子树又有可能违反最大堆的性质,所以要对该子树递归调用maxHeapify()函数。

当 maxHeapify() 函数作用在一棵以 i 为根结点的、大小为 n 的子树上时,运行时间为调整A[i]、A[left]、A[right] 的时间 O(1),加上对以 i 为某个子结点为根的子树递归调用 maxHeapify 的时间。i 结点为根的子树大小最多为 2n/3(最底层刚好半满的时候),所以可以推得 T(N) = T(2N/3) + O(1),所以 T(N)=O(lgN)。

下图是一个运行 maxHeapify(heap, 2) 的例子。A[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1},堆大小为 10。

【42期】盘点那些必问的数据结构算法题之二叉堆

3 建立最大堆

我们可以知道,数组 A[0, 1, …, N-1] 中,A[N/2, …, N-1] 的元素都是树的叶结点。如上面图中的 6-10 的结点都是叶结点。每个叶子结点可以看作是只含一个元素的最大堆,因此我们只需要对其他的结点调用 maxHeapify() 函数即可。


void buildMaxHeap(int A[], int n)
{
    int i;
    for (i = n/2-1; i = 0; i--) {
        maxHeapify(A, i, n);
    }
}

之所以这个函数是正确的,我们需要来证明一下,可以使用循环不变式来证明。

循环不变式:在for循环开始前,结点 i+1、i+2…N-1 都是一个最大堆的根。

初始化:for循环开始迭代前,i = N/2-1, 结点 N/2, N/2+1, …, N-1都是叶结点,也都是最大堆的根。

保持:因为结点 i 的子结点标号都比 i 大,根据循环不变式的定义,这些子结点都是最大堆的根,所以调用 maxHeapify() 后,i 成为了最大堆的根,而 i+1, i+2, …, N-1仍然保持最大堆的性质。

终止:过程终止时,i=0,因此结点 0, 1, 2, …, N-1都是最大堆的根,特别的,结点0就是一个最大堆的根。

【42期】盘点那些必问的数据结构算法题之二叉堆

虽然每次调用 maxHeapify() 时间为 O(lgN),共有 O(N) 次调用,但是说运行时间是 O(NlgN) 是不确切的,准确的来说,运行时间为 O(N),这里就不证明了,具体证明过程参见《算法导论》。

4 堆排序

开始用 buildMaxHeap() 函数创建一个最大堆,因为数组最大元素在 A[0],通过直接将它与A[N-1] 互换来达到最终正确位置。去掉 A[N-1],堆的大小 heapSize 减1,调用maxHeapify(heap, 0, –heapSize) 保持最大堆的性质,直到堆的大小由N减到1。


void heapSort(int A[], int n)
{
    buildMaxHeap(A, n);
    int heapSize = n;
    int i;
    for (i = n-1; i = 1; i--) {
        swapInt(A, 0, i);
        maxHeapify(A, 0, --heapSize);
    }
}

5 优先级队列

最后实现一个最大优先级队列,主要有四种操作,分别如下所示:

  • **insert(PQ, key):**将 key 插入到队列中。
  • **maximum(PQ):**返回队列中最大关键字的元素
  • **extractMax(PQ):**去掉并返回队列中最大关键字的元素
  • **increaseKey(PQ, i, key):**将队列 i 处的关键字的值增加到 key
  • 这里定义一个结构体 PriorityQueue 便于操作。

    
    typedef struct PriorityQueue {
        int capacity;
        int size;
        int elems[];
    } PQ;
    

    最终优先级队列的操作实现代码如下:

    
    /**
     * 从数组创建优先级队列
     */
    PQ *newPQ(int A[], int n)
    {
        PQ *pq = (PQ *)malloc(sizeof(PQ) + sizeof(int) * n);
        pq-size = 0;
        pq-capacity = n;
    
        int i;
        for (i = 0; i  pq-capacity; i++) {
            pq-elems[i] = A[i];
            pq-size++;
        }
        buildMaxHeap(pq-elems, pq-size);
    
        return pq;
    }
    
    int maximum(PQ *pq)
    {
        return pq-elems[0];
    }
    
    int extractMax(PQ *pq)
    {
        int max = pq-elems[0];
        pq-elems[0] = pq-elems[--pq-size];
        maxHeapify(pq-elems, 0, pq-size);
        return max;
    }
    
    PQ *insert(PQ *pq, int key)
    {
        int newSize = ++pq-size;
        if (newSize  pq-capacity) {
            pq-capacity = newSize * 2;
            pq = (PQ *)realloc(pq, sizeof(PQ) + sizeof(int) * pq-capacity);
        }
        pq-elems[newSize-1] = INT_MIN;
        increaseKey(pq, newSize-1, key);
        return pq;
    }
    
    void increaseKey(PQ *pq, int i, int key)
    {
        int *elems = pq-elems;
        elems[i] = key;
    
        while (i  0 && elems[PARENT(i)]  elems[i]) {
            swapInt(elems, PARENT(i), i);
            i = PARENT(i);
        }
    }
    

    参考资料

    算法导论第6章《堆排序》

    来源:juejin.im/post/5b9e6341e51d450e51626374

    最近三期

    与其在网上拼命找题?** 不如马上关注我们~**

    【42期】盘点那些必问的数据结构算法题之二叉堆

    原文始发于微信公众号(Java面试题精选):

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    转载声明:转载请注明出处,本技术博客是本人原创文章

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> 【42期】盘点那些必问的数据结构算法题之二叉堆


     上一篇
    【41期】盘点那些必问的数据结构算法题之链表 【41期】盘点那些必问的数据结构算法题之链表
    点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。 0 概述链表作为一种基础的数据结构,在很多地方会用到。如在Linux内核代码,red
    2021-04-05
    下一篇 
    【44期】盘点那些必问的数据结构算法题之二分查找算法 【44期】盘点那些必问的数据结构算法题之二分查找算法
    点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。 0 概述二分查找本身是个简单的算法,但是正是因为其简单,更容易写错。甚至于在二分查找
    2021-04-05