数据结构——堆(C语言)

简介: 数据结构——堆(C语言)

本篇会解决一下几个问题:

1.堆是什么?

2.如何形成一个堆?

3.堆的应用场景

 堆是什么?

  • 堆总是一颗完全二叉树
  • 堆的某个节点总是不大于或不小于父亲节点

如图,在小堆中,父亲节点总是小于孩子节点的。

如图,在大堆中,父亲节点总是大于孩子节点的。

堆和二叉树还是有很大区别的,堆是用数组来实现的,尽管逻辑结构上是一颗二叉树,但在内存上要比二叉树好,普通的二叉树,你要用链表来存储他们的左右孩子,还要给他们分配空间,但堆只是用数组来表示。

如何形成一个堆?

堆的创建有向上调整和向下调整两种方式。

向上调整:从第一个非叶子节点开始向上调整,一直调整到根节点。

用int a[] ={1,5,3,8,7,6};来做例子,

如图所示,


向下调整:从根节点开始,和左右孩子中小或者大的节点比较,交换,直到小于数组元素。

堆的插入


堆的删除

删除堆是删除堆顶的元素,将堆顶的元素根据最后一个数据一换,然后删除数组中最后一个元素,再进行向下调整算法。

这里想一想为什么要这样???

1.因为堆是有数组来创建的,如果直接删除堆顶的数据,第一个缺点就是会造成移动,从后往前覆盖,这样就会造成一个问题。兄弟节点变成父子节点,而且这样也不能很好的利用数组的优点。

2.如果是交换第一个和最后一个元素,这样有2个优点:

  • 第一个是不会破坏除了堆顶的左右堆的结构。
  • 第二个就是会利用数组的优点,数组读取速度很快,这样每次最后或最小的元素就放在了后面。

堆的时间复杂度

向下调整时间复杂度:


则要移动节点的总步数为:


向上调整时间复杂度:

则要移动节点的总步数为:

堆的应用场景

  1. 堆排序,可以用堆的建立和堆的删除来实现排序,堆排序十分稳定(相同元素的相对位置不会发生交换),而且时间复杂度都是O(N*logN)
  2. TOP-K问题,我们想一想王者荣耀中前100的玩家是怎么实现的,或者专业前10名...问题

1).先回答一下TOP-K问题:即求数据结合中前K个最大的元素或最小的元素,一把情况下数据很大。

2).对于这种场景,首先想到的就是排序,但是:数据非常大,排序就不可取了,因为内存大小的原因,不会全部加载到内存,这时堆就发生了巨大的优势。


思路:利用K个元素建堆,如果是求最大的K个元素,就建立小堆,求最小的K歌元素,就建立大堆。然后用N-K个元素与堆顶元素比较,满足条件就交换。

下面是源码:

void HeapInit(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->size = php->capacity =0;
}
void HeapDestroy(Heap* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = php->size =0;
}
void Swap(HeapDateType* child, HeapDateType* parent){
  HeapDateType tmp = *child;
  *child=  *parent;
  *parent = tmp;
}
void AdjustUp(HeapDateType* a,int child){
  int parent = (child-1)/2;
  while(child > 0){
    if(a[child] < a[parent]){
      Swap(&a[child],&a[parent]);
      child = parent;
      parent = (child-1)/2;
    }else{
      break;
    }
}
}
void HeapPush(Heap* php,HeapDateType x)
{
  assert(php);
  if(php->size == php->capacity){
  int newCapacity = php->capacity == 0?4:php->capacity*2;
  HeapDateType* tmp = (HeapDateType*)realloc(php->a,sizeof(HeapDateType)*newCapacity);
  if(tmp == NULL){
    perror("realloc fail\n");
  }
  php->a = tmp;
  php->capacity = newCapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a,php->size-1);
}
void HeapPrint(Heap* php)
{
  assert(php);
  for(size_t i =0; i<php->size; i++){
    std::cout << php->a[i] << " ";
  }
  std::cout << std::endl;
}
void AdjustDown(HeapDateType* a,int n, int parent)
{
  int child = parent*2+1;
  while(child < n){
    if(child+1 < n && a[child+1] < a[child]){
      child++;
    }
    if(a[child] < a[parent]){
      Swap(&a[child],&a[parent]);
      parent = child;
      child = parent*2+1;
    }else{
      break;
    }
  }
}
HeapDateType HeapTop(Heap* php)
{
  assert(php);
  assert(php->size > 0);
  return php->a[0];
}
void HeapPop(Heap* php)
{
  assert(php);
  assert(php->size > 0);
  Swap(&php->a[0],&php->a[php->size-1]);
  --php->size;
  AdjustDown(php->a,php->size,0);
}
bool HeapEmpty(Heap* php)
{
 assert(php);
 return php->size == 0;
}
void HeapSort(int* a, int n)
{
  //向上调整 O(n*logn)
//  for(size_t i =1; i<n; i++){
//    AdjustUp(a,i);
//  }
//
  //向下调整 O(n)
  for(int i = (n-2)/2; i>=0; i--){
    AdjustDown(a,n,i);
  }
  //时间复杂度O(N*logN)
  int end = n-1;
  while(end > 0){
    Swap(&a[0],&a[end]);
    AdjustDown(a,end,0);
    --end;
  }
}
void PrintTopK(const char* filename,int k)
{
  FILE* fout = fopen(filename,"r");
  if(fout == NULL){
    perror("fopen fail");
    exit(-1);
  }
  int* minHeap = (int*)malloc(sizeof(int)*k);
  if(minHeap == NULL){
    perror("malloc fail");
    exit(-1);
  }
  for(int i =0; i<k; i++){
    fscanf(fout,"%d",&minHeap[i]);
  }
  for(int i = (k-2)/2; i>=0; i++){
    AdjustDown(minHeap,k,0);
  }
  int x =0;
  while(fscanf(fout,"%d",&x)!= EOF){
    if(x > minHeap[0]){
      minHeap[0] = x;
      AdjustDown(minHeap,k,0);
    }
  }
  for(int i =0; i<k; i++){
    std::cout << minHeap[i] << " ";
  }
  std::cout << std::endl;
}


相关文章
|
11月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
426 1
|
11月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
147 4
|
11月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
124 4
|
11月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
116 4
|
11月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
145 4
|
11月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
137 4
|
11月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
104 4
|
11月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例,包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法,涵盖了链表操作的多种场景,旨在帮助读者深入理解链表数据结构的应用,提升算法设计与编程能力。
131 4
|
8月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。