[数据结构]——二叉树——堆排序

简介: [数据结构]——二叉树——堆排序

后续代码以此为基础


typedef int HPDataTyp;
typedef struct Heap
{
  HPDataTyp * a;
int size;
int capacity;
} Hp;

1.首先我们需要掌握两种堆算法


1,堆向下调整算法


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


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

image.png


代码实现:改一下比较大小便实现大小堆

a,表示需要调整的数组;size表示数组的大小;parent表示需要调整的节点的下标。


计算出左孩子的下标child = parent * 2 + 1。


将较小的节点上浮到正确的位置


1.实现小堆

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

2.实现大堆

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

2,堆向上调整算法

堆向上调整算法是一种用于维护堆的性质的算法,通常用于在插入元素或者修改元素值后,将堆重新调整为满足堆性质的状态。堆向上调整算法的基本思想是,从插入或修改的位置开始,向上比较并交换元素,直到满足堆的性质为止。


具体步骤如下:


   1.将新插入或修改的元素放置在堆的最后一个位置。


    2.比较该元素与其父节点的大小关系,如果不满足堆的性质(大顶堆要求父节点大于等于子节点,小顶堆要求父节点小于等于子节点),则交换两者的位置。


  3.重复步骤2,直到满足堆的性质为止。


下图为堆向上调整算法的示意图:


        10

      /    \

     7      9

    / \    / \

   6   5  8   4


插入元素3后,堆如下所示:

        10

      /    \

     7      9

    / \    / \

   6   5  8   4

  /

 3


经过堆向上调整算法调整后,堆如下所示:

        10

      /    \

     7      9

    / \    / \

   6   5  8   4

  / \

 3   3


代码实现 :

1.实现小堆

void adjustup(HPDataTyp* 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;
  }
  }
}

2.实现大堆

2.. 建堆



1.升序:建大堆

for (int i = 0; i <n; ++i)
  {
  adjustup(a,i);
  }

2.降序:建小堆

for (int i = (n-1 -1) / 2; i >= 0; --i)
  {
  adjustdown(a, n, i);
  }

3.排序


————————————————使用实现小堆的代码——————————————————


1.降序

void heapSort(int* a, int n)
{
  for (int i = 1; i <n; i++)
  {
  adjustup(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
   Swap(&a[0], &a[end]);
  adjustdown(a, end, 0);
  --end;
  }
}

或者

void heapSort(int* a, int n)
{
  for (int i = 1; i <n; i++)
  {
  adjustup(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
   Swap(&a[0], &a[end]);
  adjustdown(a, end, 0);
  --end;
  }
}

image.png

2.升序

————————————————使用实现大堆的代码——————————————————


和降序的看似代码一样,只不过大小堆区别一定要分清


void heapSort(int* a, int n)
{
  for (int i = 1; i <n; i++)
  {
  adjustup(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
   Swap(&a[0], &a[end]);
  adjustdown(a, end, 0);
  --end;
  }
}


void heapSort(int* a, int n)
{
  for (int i = 1; i <n; i++)
  {
  adjustup(a, i);
  }
  int end = n - 1;
  while (end > 0)
  {
   Swap(&a[0], &a[end]);
  adjustdown(a, end, 0);
  --end;
  }
}

image.png

相关文章
|
1天前
|
存储
数据结构——二叉树
数据结构——二叉树
TU^
|
1天前
|
存储 算法
数据结构~~链式二叉树
数据结构~~链式二叉树
TU^
3 0
|
5天前
|
存储
数据结构初阶 初识二叉树
数据结构初阶 初识二叉树
7 0
|
9天前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
8 0
|
10天前
|
算法
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
10 0
|
10天前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
12 0
|
10天前
|
存储 算法
数据结构和算法学习记录——二叉树的非递归遍历(中序遍历、先序遍历、后序遍历)
数据结构和算法学习记录——二叉树的非递归遍历(中序遍历、先序遍历、后序遍历)
11 0
|
10天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
9 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
10天前
|
算法
数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)
数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)
6 0
|
10天前
深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作
深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作
12 0