数据结构-堆的实现及应用(堆排序和TOP-K问题)（下）-阿里云开发者社区

五.建堆

上面的代码可以让我们从无到有建立堆

但是如果我们要把一个数组改造成堆,而且不能浪费其他空间,只能在原数组上改造,那该怎么办呢?

这里我们需要建堆

这里以建小堆为例

1.自顶向下的建堆方式(利用向上调整算法)

根据上文可知进行向上调整算法后,数组中[0,child]区间就变为小堆了,所以我们可以用一个for循环来扩展这个区间让这个区间从[0,1]一直扩到[0,n-1]

于是我们可以写出如下代码

for (int i = 1; i < n; i++)
  {
    AdjustUp(arr, i, cmp_up);
  }
• 1

下面给大家画张图看一看:

2.自底向上的建堆方式(利用向下调整算法)

既然向上调整算法可以建堆,那么向下调整算法呢?

答案是:也可以建堆

我们可以从最后一个非叶子节点往上建堆,先让下面变成小堆,再让上面变成小堆

那么我们该如何求出最后一个非叶子节点呢?

根据堆的特性,我们得出过如下结论:

parent=(child-1)/2;

parent自然是非叶子节点,那么我们只需要求出最后一个parent不就行了吗?

我们又知道最后一个child的下标一定是n-1

所以得出最后一个parent的下标是(n-1-1)/2;

根据上文我们得出向下调整算法可以使得

数组中区间[root,n)范围内变为小堆

那么我们就可以逐步扩大这个范围,让这个范围从[(n-1-1)/2,n)一直扩大到[0,n)

所以我们可以写出如下代码

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, i, n, cmp_down);
  }

下面给大家画张图看一看:

3.两种方法建堆的时间复杂度

//向下调整算法
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, i, n, cmp_down);
  }
//向上调整算法
  for (int i = 1; i < n; i++)
  {
    AdjustUp(arr, i, cmp_up);
  }

可能大家看到这两个代码后的反应是:

因为向上和向下调整算法的时间复杂度都是log(2)N

所以这两种建堆的时间复杂度不都是O(Nlog2(N))吗?
答案是:并不是这样,
向下调整算法建堆的时间复杂度:O(N)
向上调整算法建堆的时间复杂度:O(Nlog(2)N)

下面我们来用数学公式证明一下(这里需要用到错位相减法)

1.向下调整算法建堆的时间复杂度

2.向上调整算法建堆的时间复杂度

前面已经介绍了如何把一个普通的数组改造成堆

那么接下来我们来看堆的两大重要应用:

堆排序和TOP-K问题

六.堆排序

1.算法思想

1.那么排升序我们要建什么堆呢?

答案是:大堆,这个答案确实挺出人意料的,但是为什么呢?

下面我们来详细解释一下这个原因

1.建小堆为什么不可以(不建议):

2.建大堆为什么可以(建议):

因为:

堆排序是属于选择排序的一种.

如果是建小堆,最小数在堆顶,已经被选出来了,

那么在剩下的数中再去选数,但是剩下的树结构都乱了,需要重新建堆才能选出下一个数,

建堆的时间复杂度是O(N),我们在讲解堆排序的最后会给大家证明这个建堆的时间复杂度.

那么这样不是不可以,但是堆排序就没有效率优势了并且建堆选数还不如直接遍历选数

其次,如何选次小的数呢?

第二个数去做根了,剩下的树关系全乱了,再重新建堆,

建堆的时间复杂度:O(N),而建堆选数排序,时间复杂度:O(N^2)

并且建堆选数还不如直接遍历选数

下面我给大家画图来演示一下:

2.建大堆:

步骤:

1.第一个和最后一个交换,然后把交换后的那个较大的数(即位于数组末尾的那个数)不看做堆里面

2.前n-1和数进行向下调整算法,选出次大的数放到根节点,再跟倒数第二个位置交换

2.代码实现

代码如下:

void HeapSort(int* a,int n)
{
  int i = 0;
  //这里用向下调整算法来建堆,因为时间复杂度只有O(N)
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustUp(a, end, 0);
    --end;
  }
}

下面给大家画图演示一下,能帮助大家有更好的理解

3.时间复杂度

void HeapSort(int* a,int n)
{
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustUp(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustUp(a, end, 0);
    --end;
  }
}

向下调整算法最坏的情况:进行高度次,即log(2)N次,所以while循环最坏进行了(n-1)log(2)N次,而for循环的建堆的时间复杂度为O(N)
所以整体的时间复杂度为O(Nlog(2)N)

整个效率相对来说是很高的

4.稳定性

堆排序是不稳定的

因为建堆的时候有可能发生以下的类似情况

七.TOP-K问题

可能很多小伙伴有这么一个疑问:什么是TOP-K问题啊?

TOP-K问题:

就是求数据集合中前K个最大或者最小的元素,一般情况下数据量都比较大

比如:

全国企业500强,专业前10名,全国高考前100名等等…

那么我们如何利用堆来解决TOP-K问题呢?

假设有10亿个数据,内存存不下,数据在文件中
找出最大的前K个,  K==100
1.读取文件的前100个数据,在内存数组中建立一个小堆
2.再依次读取剩下的数据,跟堆顶数据比较,大于堆顶,就替换它进堆,向下调整
3.所有数据读取完毕,堆里面的数据就是最大的前100个

那么我们要建小堆还是大堆呢?

答案是:找最大的前K个就建小堆

反之,建大堆

为什么不建议建大堆:
大堆只能找出最大的一个数,
而且最大的数会挡在根节点的位置,后面的数完全无法进堆,那就完蛋了
小堆的优势
而小堆的话,只有第K个大的数才会挡在根节点的位置,而更大的数会往堆的下面跑
时间复杂度O(N*logK),而且K相对于N来说可以忽略不计,所以可以认为是O(N)
时间复杂度:O(K),K:堆的大小,而K相对于N来说可以忽略不计,所以可以认为是O(1)

下面我们结合一道leetcode题目来实现一下这个代码

八.一道与TOP-K相关的leetcode题目

最小K个数

void Swap(int*p1,int*p2)
{
     int tmp =*p1;
     *p1 = *p2;
     *p2 = tmp;
}
//前k个数建大堆
//向下调整算法
 void AdjustDown(int*a,int n,int parent)
 {
     int minchild = parent*2+1;
     while(minchild<n)
     {
         if(minchild+1<n&&a[minchild+1]>a[minchild])
         {
             minchild++;
         }
         if(a[minchild]>a[parent])
         {
             Swap(&a[minchild],&a[parent]);
             parent = minchild;
             minchild = parent*2+1;
         }
         else
         {
             break;
         }
     }
 }
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
    if(k==0)
    {
        *returnSize=0;
        return NULL;
    }
    int* ret=(int*)malloc(sizeof(int)*k);
    for(int i=0;i<k;i++)
    {
        ret[i]=arr[i];
    }
    //前k个数建大堆
    for(int i=(k-1-1)/2;i>=0;i--)
    {
        AdjustDown(ret,k,i);
    }
    for(int i=k;i<arrSize;i++)
    {
        if(ret[0]>arr[i])
        {
            ret[0]=arr[i];
            AdjustDown(ret,k,0);
        }
    }
    *returnSize=k;
    return ret;
}

九.测试TOP-K对于海量数据的处理

下面我们来测试一下TOP-K对于大数据的处理功能

//创建一个文件，并且随机生成一些数字
void CreateDataFile(const char* filename, int N)
{
  FILE* Fin = fopen(filename, "w");
  if (Fin == NULL)
  {
    perror("fopen fail");
    exit(-1);
  }
  srand(time(0));
  for (int i = 0; i < N; i++)
  {
    fprintf(Fin, "%d ", rand() % 10000);
  }
}
void PrintTopK(const char* filename, int k)
{
  assert(filename);
  FILE* fout = fopen(filename, "r");
  if (fout == NULL)
  {
    perror("fopen fail");
    return;
  }
  int* minheap = (int*)malloc(sizeof(int) * k);
  if (minheap == NULL)
  {
    perror("malloc fail");
    return;
  }
  //读前k个数
  for (int i = 0; i < k; i++)
  {
    //空格和换行默认是多个值之间的间隔
    fscanf(fout, "%d", &minheap[i]);
  }
  //建k个数的堆
  for (int j = (k - 1 - 1) / 2; j >= 0; j--)
  {
    AdjustDown(minheap, j, k, cmp_down);
  }
  //读取后N-K个
  int x = 0;
  while(fscanf(fout,"%d",&x)!=EOF)
  {
    if (x > minheap[0])
    {
      minheap[0] = x;
      AdjustDown(minheap, 0, k, cmp_down);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minheap[i]);
  }
  printf("\n");
  free(minheap);
  fclose(fout);
}
int main()
{
  //CreateDataFile("data.txt", 1000000);
  //找前10个最大的数
  PrintTopK("data.txt", 10);
  return 0;
}

我们已经提前修改了文件当中的值,

现在文件当中的最大的前10个值是1000000到1000009

运行后的结果:

可见堆针对于TOP-K的强大之处

十.总结

本文介绍了

1.堆的知识点

2.用C语言实现了堆

3.并且用函数指针实现了回调函数对向上和向下调整算法的代码进行了优化

4.实现了建堆

5.用数学公式推导出了两种建堆方法的时间复杂度

6.实现了堆排序

7.分析了堆排序的时间复杂度和稳定性

8.介绍了TOP-K的代码实现并解决了一道leetcode题目

9.测试了TOP-K对于大数据的处理功能

以上就是<<数据结构-堆的实现及应用>>的讲解,希望能对大家有所帮助,谢谢大家!

数据结构-堆的实现及应用(堆排序和TOP-K问题)（下）