[数据结构] ——堆及其应用

[bigshot]

一、堆 先说说堆概念：如果有一个关键码的集合 K = {k0，k1，k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >=K2i+1 且 Ki >= K2i+2) i =0，1，2 …，则称为小堆(或大堆)。

小堆(大堆)中：任一结点的关键码均小于(大于)等于它的左右孩子的关键码，位于堆顶结点的关键码最小(最大)，从根节点到每个结点的路径上数组元素组成的序列都是递增(递减)的堆存储在下标为 0 开始的数组中，因此在堆中给定下标为 i 的结点时：如果 i=0，结点 i 是根节点，没有双亲节点；否则结点 i 的双亲结点为结点(i-1)/2 如果 2 * i + 1 <= n - 1，则结点 i 的左孩子为结点 2 * i + 1，否则结点 i 无左孩子如果 2 * i + 2 <= n - 1，则结点 i 的右孩子为结点 2 * i + 2，否则结点 i ①大小堆的构建 将二叉树调整为最小堆的原理： 从最后一个非叶子结点开始调整，一直到根节点为止，将每个结点及其子树调整到满足小堆的性质即可。 代码如下：

void AdjustDown(DataType* a, size_t n, int root) //向下调整
{
    int parent = root;
    int child = parent*2 + 1;
    while (child<(int)n)
    {
        if(a[child]>a[child+1] && child+1 <(int)n)
            ++child;

        if (a[child]<a[parent])
            Swap(&a[child],&a[parent]);
        else
            break;

        parent = child;
        child = parent*2 + 1;
    }
}
void MakeSmallHeap(DataType* a, size_t n) //构建小堆
{
    int i = (n-2)>>1;
    for (; i >= 0; --i)
    {
        AdjustDown(a,n,i);
    }
}

大堆与小堆原理相同，代码相似，此处不再赘述。 ②堆的插入和删除 插入 其实在一个堆中是可以在任意位置插入和删除结点的，为了高效起见我们在插入一个结点时我们将该结点尾插到存储堆结构的顺序表中，如果我们插入的结点比原来的大堆中的所有数据都大的话我们就破坏了原来的大顶堆的结构了，此时我们就需要调整新堆的，在这里用的是向上调整的算法. 插入数据的时间复杂度为 O(lgn). 向上调整代码：

void AdjustUp(DataType* a,int child) //向上调整
{
    int parent = (child-1)>>1;
    while (child >0)
    {
        if (a[parent] > a[child] && parent >= 0)
            Swap(&a[child],&a[parent]);
        else
            break;

        child = parent;
        parent = (child-1)>>1;
    }
}

删除 1).将最后一个结点的数据域与堆顶的元素交换. 2).删除最后一个结点，此时删除的就是原来的堆顶元素 3).向下调整删除之后的堆，使其继续满足大顶堆的定义. 删除数据的时间复杂度为 O(lgn). 插入和删除的算法会在堆的应用中写道，此处不再赘述。 堆的应用 ①优先级队列 我们知道队列的特性是先进先出，那什么是优先级队列呢？在某一情况下队列的先进先出并不能满足我们的需求，我们需要优先级高的先出队列，这就类似 VIP 之类的. 下面给出实现优先级队列的两种思路: 想法一: Push:在需求的优先级的位置插入数据，时间复杂度为 O(n). Pop:直接从队头删除数据，时间复杂度为 O(1). 想法二: Push:直接插在队尾，时间复杂度为 O(1). Pop:找到优先级最高的元素删除,时间复杂度为 O(n). 在实际应用中第一种想法是优于第二种想法的,但是其实还有一种更加高效的方法，那就是用堆实现优先级队列 函数代码：

void PriorityQueuePush(PriorityQueue* q, DataType x)
{
    assert(q);
    if (q->_size == N)
        return;

    q->_a[q->_size] = x;
    q->_size++;
    
    AdjustUp(q->_a,q->_size-1);
}

void PriorityQueuePop(PriorityQueue* q)
{
    assert(q);
    if (q->_size == 0)
        return;

    q->_a[0] = q->_a[q->_size-1];
    q->_size--;

    AdjustDown(q->_a,q->_size,0);
}

DataType PriorityQueueTop(PriorityQueue* q)
{
    if (PriorityQueueEmpty(q))
        return q->_a[0];
}

size_t PriorityQueueSize(PriorityQueue* q)
{
    assert(q);
    return q->_size;
}

size_t PriorityQueueEmpty(PriorityQueue* q) 
{
    assert(q);
    if (q->_size > 0)
        return 1;
    else
        return 0;
}

头文件和测试代码在结尾给出。 ②topk 问题（构建相反堆找出前 k 个数） 在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最好的前 k 个数，或者从海量数据中找出最大的前 k 个数，这类问题通常被称为 top K 问题。例如，在搜索引擎中，统计搜索最热门的 10 个查询词；在歌曲库中统计下载最高的前 10 首歌等。

维护一个 K 个数据的小顶堆，遍历元素，若元素大于堆顶元素，则将堆顶元素移除，当前元素插入堆顶，并进行调整。 代码实现

void TopK(DataType* a, size_t n, size_t k) //topk 问题
{
    size_t i = k;
    MakeSmallHeap(a,k); //构建小堆
    
    for (i=k; i<n; i++) //遍历剩下的数
    {
        if (a[i]>a[0])
        {
            a[0] = a[i];
            AdjustDown(a,k,0);//向下调整
        }
    }

    for (i=0; i<k; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

头文件和测试代码在结尾给出。 ③堆排序（升序 — 构建大堆 降序 — 构建小堆） 堆排序：先建立一个最大堆。然后将最大堆的 a[0]与 a[n]交换，然后从堆中去掉这个节点 n，通过减少 n 的值来实现。剩余的节点中，新的根节点可能违背了最大堆的性质，因此需要调用向下调整函数来维护最大堆。

函数代码：

void HeapSort(DataType* a, size_t n)  //堆排序
{
    MakeBigHeap(a,n); //构建大堆

    while (n>0)
    {
        Swap(&a[0],&a[n-1]);
        n--;
        AdjustDown(a,n,0);
    }

}

头文件和测试代码在结尾给出。

Head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include<string.h>

typedef int DataType; 

//构建大小堆
void AdjustDown(DataType* a, size_t n, int root);
void MakeBigHeap(DataType* a, size_t n);
void MakeSmallHeap(DataType* a, size_t n);
void AdjustUp(DataType* a,int child);

// topk 最大的前 K 
void TopK(DataType* a, size_t n, size_t k);

//优先级队列问题
#define N 1000 

typedef struct PriorityQueue 
{ 
    DataType _a[N]; 
    size_t _size; 

}PriorityQueue; 

void PriorityQueueInit(PriorityQueue* q);  //初始化
void PriorityQueuePush(PriorityQueue* q, DataType x); //入队
void PriorityQueuePop(PriorityQueue* q); //出队
DataType PriorityQueueTop(PriorityQueue* q); 
size_t PriorityQueueSize(PriorityQueue* q); 
size_t PriorityQueueEmpty(PriorityQueue* q); 

void HeapSort(DataType* a, size_t n); //堆排序

#endif //__HEAD_H__

Head.c

#include "Heap.h"

static void Swap(int *child,int *parent)  //交换函数
{
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

void AdjustDown(DataType* a, size_t n, int root) //向下调整
{
    int parent = root;
    int child = parent*2 + 1;
    while (child<(int)n)
    {
        if(a[child]<a[child+1] && child+1 <(int)n)
            ++child;

        if (a[child]>a[parent])
            Swap(&a[child],&a[parent]);
        else
            break;

        parent = child;
        child = parent*2 + 1;
    }
}
void MakeBigHeap(DataType* a, size_t n) //构建大堆
{
    int i = (n-2)>>1;
    for (; i >= 0; --i)
    {
        AdjustDown(a,n,i);
    }
}

void MakeSmallHeap(DataType* a, size_t n) //构建小堆
{
    int i = (n-2)>>1;
    for (; i >= 0; --i)
    {
        AdjustDown(a,n,i);
    }
}

void AdjustUp(DataType* a,int child) //向上调整
{
    int parent = (child-1)>>1;
    while (child >0)
    {
        if (a[parent] > a[child] && parent >= 0)
            Swap(&a[child],&a[parent]);
        else
            break;

        child = parent;
        parent = (child-1)>>1;
    }
}

void TopK(DataType* a, size_t n, size_t k) //topk 问题
{
    size_t i = k;
    MakeSmallHeap(a,k);
    
    for (i=k; i<n; i++)
    {
        if (a[i]>a[0])
        {
            a[0] = a[i];
            AdjustDown(a,k,0);
        }
    }

    for (i=0; i<k; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

void PriorityQueueInit(PriorityQueue* q)
{
    assert(q);
    memset(q->_a,0,sizeof(DataType)*N);
    q->_size = 0;
}

void PriorityQueuePush(PriorityQueue* q, DataType x)
{
    assert(q);
    if (q->_size == N)
        return;

    q->_a[q->_size] = x;
    q->_size++;
    
    AdjustUp(q->_a,q->_size-1);
}

void PriorityQueuePop(PriorityQueue* q)
{
    assert(q);
    if (q->_size == 0)
        return;

    q->_a[0] = q->_a[q->_size-1];
    q->_size--;

    AdjustDown(q->_a,q->_size,0);
}

DataType PriorityQueueTop(PriorityQueue* q)
{
    if (PriorityQueueEmpty(q))
        return q->_a[0];
}

size_t PriorityQueueSize(PriorityQueue* q)
{
    assert(q);
    return q->_size;
}

size_t PriorityQueueEmpty(PriorityQueue* q) 
{
    assert(q);
    if (q->_size > 0)
        return 1;
    else
        return 0;
}

void HeapSort(DataType* a, size_t n)  //堆排序
{
    MakeBigHeap(a,n);

    while (n>0)
    {
        Swap(&a[0],&a[n-1]);
        n--;
        AdjustDown(a,n,0);
    }

}

Test.c

#include "Heap.h"

void Test1()
{ 
    int  i = 0;
    DataType a[] = {16, 18, 15, 17, 14, 19,10,11, 13, 12};
    MakeSmallHeap(a, sizeof(a)/sizeof(DataType));
    MakeBigHeap(a, sizeof(a)/sizeof(DataType)); 

    DataType NArray[1000]; 
    srand((int)time(0)); 
    for (i = 0; i < 1000; ++i) 
    { 
        NArray[i] = rand()%10000; 
    } 

    NArray[30] = 10001; 
    NArray[350] = 10002; 
    NArray[999] = 10003; 
    NArray[158] = 10004; 
    NArray[334] = 10005; 

    TopK(NArray, 1000, 5); 

    HeapSort(a,sizeof(a)/sizeof(DataType));
}

void TestPriorityQueue() 
{ 
    PriorityQueue q; 
    PriorityQueueInit(&q); 
    PriorityQueuePush(&q, 5); 
    PriorityQueuePush(&q, 2); 
    PriorityQueuePush(&q, 3); 
    PriorityQueuePush(&q, 7); 
    PriorityQueuePush(&q, 6); 
    PriorityQueuePush(&q, 1); 
    PriorityQueuePush(&q, 4); 

    while (PriorityQueueEmpty(&q) != 0) 
    { 
        printf("%d ", PriorityQueueTop(&q)); 
        PriorityQueuePop(&q); 
    } 
    printf("\n"); 

} 

int main()
{
    Test1();
    TestPriorityQueue();
    return 0;
}

topk 问题测试时要巧妙构建测试案例。

csdn 地址： http://blog.csdn.net/qq_38646470/article/details/79371249