[数据结构]——二叉树——堆的实现

简介: [数据结构]——二叉树——堆的实现

1. 堆的概念及结构


如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储

在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1,

2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

堆中某个节点的值总是不大于或不小于其父节点的值;

堆总是一棵完全二叉树。

image.png

2. 堆的实现


1.堆的创建


下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。


int a[] = {1,5,3,8,7,6};

image.png


2. 建堆时间复杂度


因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):

image.png

因此:建堆的时间复杂度为O(N)。


3.堆的插入


先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。

image.png


4.堆的删除


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

image.png

5.堆向下调整算法


现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

image.png

3.代码深度解析


1.首先弄一个交换数据

交换两个指针所指向的变量的值


通过解引用操作符*,将p2指针所指向的变量的值赋给了p1指针所指向的变量,将之前存储在temp中的值赋给了p2指针所指向的变量,完成了交换。


void Swap(HPDataType *p1, HPDataType *p2)
{
    HPDataType temp = *p1;
    *p1 =*p2;
    *p2 = temp;
}

2.向上调整堆

将数组a中指定索引child的元素向上调整,使其在最小堆中满足最小堆的性质


通过计算child的父节点索引,即(parent = (child - 1) / 2),确定了父节点的位置。在循环中,child的元素比父节点的元素小调用Swap函数,将child和parent指向的元素进行交换。然后,代码更新child和parent的值,将child变为parent,parent变为(child - 1) / 2,继续循环。如果不是,即child的元素不小于父节点的元素,代码通过break语句跳出循环,这时已经完成了向上调整的操作。


void AdjudtUp(HPDataType* 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;
        }
    }
}


3.向下调整堆

调整小顶堆的算法,接受一个int类型的指针a,表示一个数组,size表示数组的大小, parent表示要调整的节点位置


void AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


4.堆的插入

堆已满,则需要扩容。然后,将原来的内存空间指针hp->_a指向新分配的内存空间,更新堆的容量为新的容量。将要插入的元素x赋值给堆的最后一个位置hp->_a[hp->_size],然后增加堆的大小hp->_size++。最后,调用AdjustUp函数将新插入的元素向上调整,以维护堆的性质


void HeapPush(Heap* hp, HPDataType  x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)
    {
        int newCapacity = hp->_capacity == 0 ? 4: hp->_capacity * 2;
        HPDataType*temp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType));
        if (temp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a =temp;
        hp->_capacity = newCapacity;
    } 
    hp->_a[hp->_size] = x;
    hp->_size++;
    AdjudtUp(hp->_a,hp->_size-1);
}


5.堆的创建

初始化后再通过for循环遍历数组a,并调用HeapPush函数将数组中的元素依次插入到堆中


void HeapCreate(Heap* hp, HPDataType *a, int n )
{
    assert(hp);
    hp->_size = 0; 
    hp->_capacity =NULL; 
    // 将数组a中的元素依次插入堆中
    for (int i = 0; i < n; i++) {
        HeapPush(hp, a[i]);
    }
}

6.堆的销毁

使用free函数释放堆的数组hp->_a的内存空间


void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_size =hp->_capacity=0;
}

7.堆的删除

调用AdjustDown()函数,从堆顶开始向下调整堆,以保持堆的性质


void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}

8.取堆顶的数据


函数返回堆中数组_a的第一个元素即堆顶的数据


取堆顶的数据

HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    return hp->_a[0];
}

9.堆的数据个数

返回堆的_size成员,即堆的大小


int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}


10. 堆的判空

通过断言assert(hp);来确保传入的参数hp不为NULL。


然后,通过判断堆的大小hp->_size是否为0来判断堆是否为空。


如果堆的大小为0,则返回1(即堆为空),否则返回0(即堆不为空)


int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}

4.总的代码


1.heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* _a;
  int _size;
  int _capacity;
}Heap;
//数据交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上堆的调整
void AdjudtUp(Heap* _a, int child);
// 向下调整堆
void AdjustDown(int* a, int size, int parent);
// 堆的构建
//void HeapCreate(Heap* hp);//, HPDataType* a, int n
 void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);


2.Heap.c

#include"Heap.h"
//交换数据
void Swap(HPDataType *p1, HPDataType *p2)
{
    HPDataType temp = *p1;
    *p1 =*p2;
    *p2 = temp;
}
//向上调整堆
void AdjudtUp(HPDataType* 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 AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType  x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)
    {
        int newCapacity = hp->_capacity == 0 ? 4: hp->_capacity * 2;
        HPDataType*temp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType));
        if (temp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a =temp;
        hp->_capacity = newCapacity;
    } 
    hp->_a[hp->_size] = x;
    hp->_size++;
    AdjudtUp(hp->_a,hp->_size-1);
}
// 堆的构建
//void HeapCreate(Heap* hp)//HPDataType* a, int n
//{
//    assert(hp);
//    hp->_size = 0; // 初始化堆的大小为0
//    hp->_capacity = 0; // 设置堆的容量为n
//    hp->_a = NULL;
//
//     将数组a中的元素依次插入堆中
//    //for (int i = 0; i < n; i++) {
//    //    HeapPush(&hp, a[i]);
//    //}
//}
void HeapCreate(Heap* hp, HPDataType *a, int n )
{
    assert(hp);
    hp->_size = 0; // 初始化堆的大小为0
    hp->_capacity =NULL; // 
    hp->_a = NULL;
    // 将数组a中的元素依次插入堆中
    for (int i = 0; i < n; i++) {
        HeapPush(hp, a[i]);
    }
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_size =hp->_capacity=0;
}
// 堆的删除
void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}


2.Test.c

#include"Heap.h"
void test()                          
{
  Heap sl;
  int a[10] = { 10,8,2,4,5,3,6,7,9,1 };
  /*HeapCreate(&sl);
  for (int i = 0;i < sizeof(a) / sizeof(int); i++)
  {
  HeapPush(&sl, a[i]);
  }*/
  HeapCreate(&sl,a, sizeof(a) / sizeof(int));
  while (!HeapEmpty(&sl)) {
  printf("%d  ", HeapTop(&sl));
  HeapPop(&sl);
  }
  printf("\n");
}
int main()
{
  test();
  return 0;
}
相关文章
|
1月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
40 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
1月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
82 4
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
85 16
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
132 8
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
100 1
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
32 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
37 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
31 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
29 1
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆