【数据结构】堆(二)——堆排序、TOP-K问题

简介: 【数据结构】堆(二)——堆排序、TOP-K问题

作者:一个喜欢猫咪的的程序员

专栏:《数据结构》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》

目录

堆排序:(以小堆为例)

Heapsort函数(堆排序):

向下调整具体的时间复杂度:

向上调整具体的时间复杂度:

如何实现堆排序

TOP-K问题


堆排序:(以小堆为例)


堆的分类:

  • 升序or降序
  • 大堆or小堆
void test2()
{//堆排序
  int array[] = { 27,15,19,18,28,34,65,49,25,37 };
  Heapsort(array, sizeof(array) / sizeof(array[0]));
  for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

Heapsort函数(堆排序):


int array[] = { 27,15,19,18,28,34,65,49,25,37 };


需将这个数组进行大堆排列,分为两种调整形式:向上调整和向下调整。


向上调整和向下调整的思想可以参考我的例外一篇博客:http://t.csdn.cn/YFSpd

void Ajustup(HPDataType*a, int child)
{//N*logN
  assert(a);
  //int child = n - 1;
  while (child > 0)
  {
    int parent = (child - 1) / 2;
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
    }
    else
    {
      break;
    }
  }
}
void Ajustdown(HPDataType* a, int n,int parent)
{//O(N)
  assert(a);
  int child = 2 * parent+1;
  while (child<n)
  {
    if (child + 1 < n && a[child] < a[child + 1])//  <假设左子树大
    {
      child++;
    }
    if (a[child] > a[parent])//>大堆,<为小堆
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

向上调整和向下调整具体的时间复杂度是多少呢?

向下调整具体的时间复杂度:

假设树高为h

第h层,有2^(h-1)个节点,需要向下调整0次(直接不算,从第h-1层开始算)。

第h-1层,有2^(h-2)个节点,需要向下调整1层。

第h-2层,有2^(h-3)个节点,需要向下调整2层。

......

第4层,有2^3个节点,需要向下调整h-4层。

第3层,有2^2个节点,需要向下调整h-3层。

第2层,有2^1个节点,需要向下调整h-2层。

第1层,有2^0个节点,需要向下调整h-1层。


当h高的次数,最多调整层数为:


F(h)=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+...+2^(h-3)*2+2^(h-2)*1+2^(h-1)*0       ——①

2*F(h)=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+...+2^(h-2)*2+2^(h-1)*1+2^(h)*0       ——②


有错位相减②-①可得:


F(h)=-2^0*(h-1)+2^1+2^2+....+2^(h-2)+2^(h-1)


F(h)=2^h-1-h                                                                                                          ——③


当树高为h时,节点总个数N为:


N=2^0+2^1+...+2^(h-2)+2^(h-1)


N=2^h-1                                                                                                                        ——④


有④可得:h=log(N+1)                                                                                           ——⑤


综合③④⑤可得:


F(N)=N-log(N+1)


  • 因此时间复杂度为O(N)


向上调整具体的时间复杂度:

在一层,需要向上调整0次

第二层,向上调整1次

第三层,向上调整2次

...

第h-1层,向上调整h-2次

第h层,向上调整h-1次

f886e5e7e3c04396882e143b447ff8aa.gif

F(h)=2^1*1+2^2*2+....+2^(h-1)*(h-1)。

由错位相减可得:

F(N)=2N(1-log(N+1))。

  • 时间复杂度为O(N*logN)

如何实现堆排序


 显然向下调整优于向上调整。

先利用Ajustdown排序好数组,然后再用交换Ajustdown实现小堆。

void Heapsort(int*a,int n)//堆排序
{//向上调整
  for (int i = 1; i <n; i++)
  {
    Ajustup(a, i);
  }
  //向下调整
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    Ajustdown(a, n, i);
  }
  int end = n - 1;
  while (end>0)
  {
    Swap(&a[0], &a[end]);
    Ajustdown(a, end, 0);
    end--;
  }
  //N*logN
}
void test2()
{//堆排序
  int array[] = { 27,15,19,18,28,34,65,49,25,37 };
  Heapsort(array, sizeof(array) / sizeof(array[0]));
  for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

TOP-K问题:


TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。


当数据量特别大时,我们造一个数组来存储他们依次存储时,就不大现实。


可以先开一个K个空间的数组,将这个数据量的前K个放进去,将他们小堆排列,并将这个数据量每个数与堆顶的元素相比较,比它大就替代它进入数组,在向下排列,以此循环。


void test3()
{
  int minHeap[5];
  FILE* fout = fopen("data.txt", "r");
  if (fout == NULL)
  {
    perror("fopen fail");
    exit(-1);
  }
  int k = sizeof(minHeap) / sizeof(minHeap[0]);
  for (int i = 0; i < k; i++)
  {
    fscanf(fout,"%d",&minHeap[i]);
  }
  for (int i = 0; i < sizeof(minHeap) / sizeof(minHeap[0]); i++)
  {//检查是否录入数据
    printf("%d ", minHeap[i]);
  }
  printf("\n");
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    Ajustdown(minHeap, k, i);
  }
  for (int i = 0; i < sizeof(minHeap) / sizeof(minHeap[0]); i++)
  {//检查是否为大小堆
    printf("%d ", minHeap[i]);
  }
  printf("\n");
  int data = 0;
  while (fscanf(fout, "%d", &data) != EOF)
  {
    if (data > minHeap[0])
    {
      minHeap[0] = data;
      Ajustdown(minHeap, k, 0);
    }
  }
  int end = k - 1;
  while (end > 0)
  {
    Swap(&minHeap[0], &minHeap[end]);
    Ajustdown(minHeap, end, 0);
    end--;
  }//完成升序或者降序
  for (int i = 0; i < sizeof(minHeap) / sizeof(minHeap[0]); i++)
  {//检查是否为大小堆
    printf("%d ", minHeap[i]);
  }
  printf("\n");
  fclose(fout);
}
void test4()
{
  int n, k;
  scanf("%d %d", &n, &k);
  FILE* fint = fopen("data1.txt", "w");
  if (fint == NULL)
  {
    perror("fopen fail");
    exit(-1);
  }
  srand(time(0));
  int randK = k;
  for (size_t i = 0; i < n; ++i)
  {
    int data = rand() % 100000;
    fprintf(fint, "%d\n", data);
  }
  fclose(fint);
  int* minHeap = (int*)malloc(sizeof(int) * k);
  FILE* fout = fopen("data1.txt", "r");
  if (fout == NULL)
  {
    perror("fopen fail");
    exit(-1);
  }
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &minHeap[i]);
  }
  for (int i = 0; i < k; i++)
  {//检查是否录入数据
    printf("%d ", minHeap[i]);
  }
  printf("\n");
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    Ajustdown(minHeap, k, i);
  }
  for (int i = 0; i < k; i++)
  {//检查是否为大小堆
    printf("%d ", minHeap[i]);
  }
  printf("\n");
  int data = 0;
  while (fscanf(fout, "%d", &data) != EOF)
  {
    if (data > minHeap[0])
    {
      minHeap[0] = data;
      Ajustdown(minHeap, k, 0);
    }
  }
  int end = k - 1;
  while (end > 0)
  {
    Swap(&minHeap[0], &minHeap[end]);
    Ajustdown(minHeap, end, 0);
    end--;
  }//完成升序或者降序
  for (int i = 0; i < k; i++)
  {//检查是否为大小堆,升序或者降序
    printf("%d ", minHeap[i]);
  }
  printf("\n");
  fclose(fout);
}
int main()
{
  //test1();
  test2();
  //test3();
  //test4();
  return 0;
}


相关文章
|
3月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
64 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
3月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
160 16
|
4月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
186 1
|
4月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
108 0
数据结构与算法学习十八:堆排序
|
4月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
4月前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
58 0
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
356 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
58 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
145 77
|
11天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。