C语言数据结构之堆排序详解

目录
  • 1.堆的概念及结构
  • 2.堆的实现
    • 2.1堆的向下调整算法
    • 2.2堆的向上调整算法
    • 2.3建堆（数组）
    • 2.4堆排序
    • 2.5堆排序的时间复杂度

1.堆的概念及结构

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树（二叉树具体概念参见——二叉树详解）的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

2.堆的实现

堆的实现请参见——二叉树详解（堆的实现）

2.1 堆的向下调整算法

（此文章都已建小堆为例）

向下调整算法前提：当前树左右子树都是小堆

核心思想：选出左右孩子中小的那个，和父亲交换，小的往上浮，大的往下沉，这里是小堆，如果是大堆则相反。

代码实现

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
//堆向下调整算法
void AdjustDown(int *a, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child<n)
    {
        //保证孩子节点child为两个孩子中的最小值；保证不越界
        if (a[child] > a[child + 1] && child+1 < n)
            ++child;
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}

2.2 堆的向上调整算法

使用场景：向上调整算法适用于向堆中插入数据，当向堆中插入数据就可能会导致堆失去大堆或者小堆的性质，此时需要重新调整，向上调整的思路与向下调整算法的思路类似，向上调整算法只需要从插入结点位置开始和父节点比较。

图示：

代码实现：

void AdjustUp(int *a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[parent] > a[child])
        {
            swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

2.3 建堆（数组）

从最后一个非叶子节点位置行依次开始调整，如图：

代码实现：

int parent = (n-2) / 2;
    //首先对每一个非叶子节点进行一次向下调整算法，保证每个非叶子节点的
    //孩子都小于它的父节点，然后可得到最小值，就在堆的顶端的父节点（也叫做建小堆）
    while (parent >= 0)
    {
        AdjustDown(a, n, parent);
        --parent;
    }

2.4 堆排序

升序建大堆，降序建小堆

void HeapSort(int *a, int n)
{
    int parent = (n-2) / 2;
    //首先对每一个非叶子节点进行一次向下调整算法，保证每个非叶子节点的
    //孩子都小于它的父节点，然后可得到最小值，就在堆的顶端的父节点（也叫做建小堆）
    while (parent >= 0)
    {
        AdjustDown(a, n, parent);
        --parent;
    }
    int end = n-1;
    while (end>0)
    {
        //将堆顶的数与最后的end,以此循环，进行交换就可得到有序序列
        //注意：建小堆，得到降序序列
        swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        --end;
    }
}

2.5 堆排序的时间复杂度

所以建堆时间复杂度为O(N)；

向下调整算法时间复杂度 O(logN)；

所以堆排序的时间复杂度为 O(N*logN)

以上就是C语言数据结构之堆排序详解的详细内容，更多关于C语言堆排序的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言实现堆排序的简单实例

    本文通过一个C语言实现堆排序的简单实例,帮助大家抛开复杂的概念,更好的理解堆排序. 实例代码如下: void FindMaxInHeap(int arr[], const int size) { for (int j = size - 1; j > 0; --j) { int parent = j / 2; int child = j; if (j < size - 1 && arr[j] < arr[j+1]) { ++child; } if (arr[child] &

  • C语言八大排序之堆排序

    C语言八大排序之堆排序

    目录 前言 一.堆排序的概念 二.堆排序的实现 第一步:构建堆 第二步:排序 三.完整代码 四.证明建堆的时间复杂度 前言 本章我们来讲解八大排序之堆排序.2022,地球Online新赛季开始了!让我们一起努力内卷吧! 一.堆排序的概念 堆排序(Heapsort):利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.通过堆来进行选择数据,需要注意的是 排升序要建大堆,排降序建小堆. 堆排序使用堆来选数,效率就高了很多. 时间复杂度: 空间复杂度: 稳定性:不稳定 二.堆排序的实

  • C语言数据结构之堆排序源代码

    C语言数据结构之堆排序源代码

    本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科: 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高了排序效率,其效率为O(n*logn). 2. 源代码 堆排序中有两个核心的操作,一个是创建大顶堆(或者小顶堆,这里用的是大顶堆),再一个就是对堆进行调整.这里需要注意的是,并没有真

  • C语言 数据结构堆排序顺序存储（升序）

    堆排序顺序存储(升序) 一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! 二:首先堆是一棵全完二叉树: a:构建一个堆分为两步:⑴创建一棵完全二叉树      ⑵调整为一个堆 (标注:大根堆为升序,小根堆为降序) b:算法描述:①创建一棵完全二叉树 ②while(有双亲){ A:调整为大根堆: B:交换根和叶子结点: C:砍掉叶子结点: } c:时间复杂度为 O(nlogn)  ,空间复杂度为 O(1), 是不稳定排序! 代码实现: /*堆排序思想:[完全二叉树的定义:前

  • C语言对堆排序一个算法思路和实现代码

    算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

  • C语言数据结构之堆排序详解

    C语言数据结构之堆排序详解

    目录 1.堆的概念及结构 2.堆的实现 2.1堆的向下调整算法 2.2堆的向上调整算法 2.3建堆(数组) 2.4堆排序 2.5堆排序的时间复杂度 1.堆的概念及结构 如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树(二叉树具体概念参见——二叉树详解)的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为小堆(或大

  • C语言数据结构之二叉树详解

    C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • C语言数据结构 快速排序实例详解

    C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart

  • C语言 数据结构平衡二叉树实例详解

    C语言 数据结构平衡二叉树实例详解

    数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

  • C语言数据结构二叉树之堆的实现和堆排序详解

    C语言数据结构二叉树之堆的实现和堆排序详解

    目录 一.本章重点 二.堆 2.1堆的介绍 2.2堆的接口实现 三.堆排序 一.本章重点 堆的介绍 堆的接口实现 堆排序 二.堆 2.1堆的介绍 一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足 每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数

  • Java语言实现数据结构栈代码详解

    近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是

  • C语言 动态内存分配详解

    C语言 动态内存分配详解 动态内存分配涉及到堆栈的概念:堆栈是两种数据结构.堆栈都是数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除. 栈(操作系统):由操作系统自动分配释放 ,存放函数的参数值,局部变量的值等.其操作方式类似于数据结构中的栈. 堆(操作系统): 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收,分配方式倒是类似于链表. \在C语言中,全局变量分配在内存中的静态存储区,非静态的局部变量(包括形参)是分配在内存的动态存储区,该存储区被

  • C语言类的双向链表详解

    C语言类的双向链表详解

    目录 前言 双向链表的定义 双向链表的创建 节点的创建 双向链表节点查找 双向链表的插入 双向链表的节点删除 双向链表的删除 总结 前言 链表(linked list)是一种这样的数据结构,其中的各对象按线性排列.数组的线性顺序是由数组下标决定的,然而于数组不同的是,链表的各顺序是由链表中的指针决定的. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循

  • C语言中自定义类型详解

    C语言中自定义类型详解

    目录 结构大小 offsetof 结构体对齐规则 存在原因 总结 结构大小 我们先随便给出一个结构体,为了计算他的大小,我给出完整的打印方案: typedef struct num { char c; int n; char cc; }num; int main() { printf("%d\n", sizeof(num)); return 0; } 好了,按道理来说我计算一个结构体大小就看他的各个成员需要消耗多大的空间, num 结构体中三个成员分别是 char ,int ,char

  • C语言二叉树的概念结构详解

    C语言二叉树的概念结构详解

    目录 1.树的概念及结构(了解) 1.1树的概念: 1.2树的表示法: 2.二叉树的概念及结构 2.1二叉树的概念 2.2特殊的二叉树 2.2二叉树的性质 2.3二叉树的顺序存储 2.4二叉树的链式存储 3.二叉树链式结构的实现 3.1二叉树的前中后序遍历 3.2求二叉树的节点个数 3.3求二叉树的叶子节点个数 3.4销毁二叉树 1.树的概念及结构(了解) 1.1树的概念: 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树

随机推荐