返回顶部
首页 > 资讯 > 精选 >堆排序的实现原理是什么
  • 515
分享到

堆排序的实现原理是什么

堆排序 2023-05-31 12:05:06 515人浏览 薄情痞子
摘要

本篇文章给大家分享的是有关堆排序的实现原理是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。对于堆排序会涉及一些完全二叉树知识。对于待排序列{10, 2, 11, 8, 7}

本篇文章给大家分享的是有关堆排序的实现原理是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

对于堆排序会涉及一些完全二叉树知识。对于待排序列{10, 2, 11, 8, 7},把它看成是一颗完全二叉树,如下图所示。

堆排序的实现原理是什么

堆分为大根堆和小根堆:大根堆表示每个根节点均大于其子节点(L(i) >= L(2i) && L(i) >= L(2i + 1)),小根堆表示每个根节点均小于其子节点(L(i) <= L(2i) && L(i) <= L(2i + 1))。(在完全二叉树中第i个节点的左子节点为2i,其右字节点为2i + 1)

本文将以大根堆的构建作为示例进行讲解。

堆排序的第一步——构建初始堆。如何构建初始堆呢?根据定义,关键点在于每个根节点。观察上述待排序列的完全二叉树,不难发现存在节点2和节点10有子节点,它们是需要关注的节点。

堆排序的实现原理是什么

如何定位节点2呢?发现它是叶子节点,或者最后一个节点的父节点,根据完全二叉树的性质可知,除根节点外任意节点的父节点的编号为&#8970;n / 2&#8971;。已知n = 5,易知节点2的编号为&#8970;5 / 2&#8971; = ②。比较它与左右子节点的大小并调整。

堆排序的实现原理是什么

最后剩下根节点10,已知节点2的编号为②,② - 1 = ①即得到根节点10的编号。比较它与左右子节点的大小并调整。

堆排序的实现原理是什么

调整完毕后发现已经构成了一个“大根堆”,示例中的待排序列较为简单,再给出一个较为复杂的待排序列,观察其构建大根堆的过程。对于待排序列{53, 17, 78, 09, 45, 65, 87, 32},将它看成一颗完全二叉树。

堆排序的实现原理是什么

同样我们来看它所需要关注的节点有哪些。

堆排序的实现原理是什么

根据第一个例子,我们很容易能定位节点09的编号为&#8970;8 / 2&#8971; = ④,节点78的编号为④ - 1 = ③……,依次类推,发现了一定的规律,即需要调整的节点位置从&#8970;n / 2&#8971;开始依次递减直到根节点①结束(&#8970;n / 2&#8971; ~ 1)。现在开始调整。

堆排序的实现原理是什么

堆排序的实现原理是什么

堆排序的实现原理是什么

堆排序的实现原理是什么

在第四次调整结束后发现节点53不满足大根堆的定义,其右子节点大于它,此时需要做进一步的向下调整。

堆排序的实现原理是什么

注意向下调整是每次向上调整的时候都需要做的判断是否需要向下调整,而不是在所有的向上调整结束过后再回过头来向下调整。这样大根堆就建立好了,此时待排序列数组情况已经发生了改变:{87, 45, 78, 32, 17, 65, 53, 09}。接下来是如何进行排序的问题。将大根堆的根节点与最后一个节点互换,并调整二叉树使其仍然满足大根堆。

堆排序的实现原理是什么

可以看到将根节点与最后一个节点呼唤后,待排序列的最大值已经放到了数组的最后一个位置{……, 87},此时完成了第一趟排序,但这第一趟排序还没有结束,此时除节点87外,其余节点并不满足大根堆的条件,所以需要对其余节点进行调整为大根堆。排序过程不再给出,Java和python3的代码实现如下。

Java

package com.alGorithm.sort.heap;import java.util.Arrays;public class Heap {    public static void main(String[] args) {    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};    nums = heapSort(nums);    System.out.println(Arrays.toString(nums));  }      private static int[] heapSort(int[] nums) {      for (int i = nums.length / 2 - 1; i >= 0; i--) {      heapAdjust(nums, i, nums.length);    }    for (int i = nums.length - 1; i > 0; i--) {      int temp = nums[i];      nums[i] = nums[0];      nums[0] = temp;      heapAdjust(nums, 0, i);    }    return nums;  }      private static void heapAdjust(int[] nums, int parent, int length) {    int temp = nums[parent];    int childIndex = 2 * parent + 1;  //完全二叉树节点i从编号1开始的左子节点位置在2i,此处数组下标从0开始,即左子节点所在数组索引位置为:2i + 1    while (childIndex < length) {      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {        childIndex++;  //节点有右子节点,且右子节点大于左子节点,则选取右子节点      }      if (temp > nums[childIndex]) {        break; //如果选中节点大于其子节点,直接返回      }      nums[parent] = nums[childIndex];      parent = childIndex;      childIndex = 2 * parent + 1;  //继续向下调整    }    nums[parent] = temp;  }}

--结束END--

本文标题: 堆排序的实现原理是什么

本文链接: https://www.lsjlt.com/news/225359.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • 堆排序的实现原理是什么
    本篇文章给大家分享的是有关堆排序的实现原理是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。对于堆排序会涉及一些完全二叉树知识。对于待排序列{10, 2, 11, 8, 7}...
    99+
    2023-05-31
    堆排序
  • C语言堆怎么实现和堆排序是什么
    这篇文章主要介绍了C语言堆怎么实现和堆排序是什么的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C语言堆怎么实现和堆排序是什么文章都会有所收获,下面我们一起来看看吧。一、本章重点堆的介绍堆的接口实现堆排序二、堆2...
    99+
    2023-06-29
  • Java排序函数的实现原理是什么
    Java中的排序函数的实现原理依赖于具体的排序算法。Java提供了多种排序算法的实现,其中包括快速排序、归并排序、插入排序等。快速排...
    99+
    2023-09-27
    Java
  • python中什么是堆排序
    python中什么是堆排序?相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。python的五大特点是什么python的五大特点:1.简单易学,开发程序时,专注的是解决问题,而不是搞...
    99+
    2023-06-14
  • 堆排序golang实现
    堆排序(Heap Sort)是一种常见的排序算法,其算法基于二叉堆的数据结构。它的时间复杂度为O(nlogn),可以用于处理大规模数据排序问题。本文将介绍golang中堆排序的实现。一、堆排序介绍堆是一种完全二叉树,其中每个节点都满足父节点...
    99+
    2023-05-15
  • golang堆排序怎么实现
    Golang堆排序的实现步骤如下: 首先,创建一个函数`heapify`用于将给定的数组或切片转换为一个最大堆。最大堆的定义是父节...
    99+
    2023-10-26
    golang
  • Golang中堆排序的实现
    堆排序 堆的概念: 堆是一棵基于数组实现的特殊的完全二叉树,这棵二叉树的每个节点的值必须大于或小于它的两个子节点。大顶堆是每个节点的值必须大于它的两个子节点,小顶堆则相反。 堆的顶点...
    99+
    2024-04-02
  • Java的堆排序、快速排序、归并排序怎么实现
    本文小编为大家详细介绍“Java的堆排序、快速排序、归并排序怎么实现”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java的堆排序、快速排序、归并排序怎么实现”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。堆排序...
    99+
    2023-06-26
  • golang归并排序,快速排序,堆排序的实现
    归并排序 归并排序使用经典的分治法(Divide and conquer)策略。分治法会将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得...
    99+
    2024-04-02
  • MySQL中排序的原理是什么
    MySQL中排序的原理是什么,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。在程序设计当中,我们很多场景下都会用 group by 关键字。...
    99+
    2024-04-02
  • redis的zset排序原理是什么
    Redis的有序集合(Sorted Set)是一种特殊类型的数据结构,它是一个无序的字符串集合,同时每个字符串都关联着一个浮点数值,...
    99+
    2023-10-23
    redis
  • Python实现的堆排序算法原理与用法实例分析
    本文实例讲述了Python实现的堆排序算法。分享给大家供大家参考,具体如下: 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的...
    99+
    2022-06-04
    算法 实例 原理
  • Java中怎么实现堆排序
    本篇文章给大家分享的是有关Java中怎么实现堆排序,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法...
    99+
    2023-06-17
  • Python3实现快速排序、归并排序、堆
    # -*- coding: utf-8 -*- # @Time : 2019-03-26 16:46 # @Author : Jayce Wong # @ProjectName : leetcode # @Fi...
    99+
    2023-01-31
    快速
  • 深入浅析java中堆排序的原理
    本篇文章为大家展示了深入浅析java中堆排序的原理,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。从堆排序的简介到堆排序的算法实现等如下:1. 简介  堆排序是建立在堆这种数据结构基础上的选择排序,是...
    99+
    2023-05-31
    java 堆排序 ava
  • MySQL排序的内部原理是什么
    MySQL排序的内部原理是什么,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。排序,排序,排序 我们通过explain查看My...
    99+
    2024-04-02
  • C++实现堆排序示例
    目录堆的实现 Heap.h 堆的管理及接口Heap.c 堆各个接口功能的实现 test.c测试堆的实现 Heap.h 堆的管理及接口 #include<stdio.h&g...
    99+
    2024-04-02
  • C++如何实现堆排序
    这篇文章主要介绍“C++如何实现堆排序”,在日常操作中,相信很多人在C++如何实现堆排序问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++如何实现堆排序”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!概述...
    99+
    2023-06-22
  • go语言堆排序怎么实现
    Go语言堆排序的实现步骤如下: 首先,定义一个用于进行堆调整的函数 adjustHeap,该函数接受三个参数:待调整的切片 arr...
    99+
    2023-10-22
    go语言
  • python堆排序算法怎么实现
    堆排序算法的实现步骤如下: 构建最大堆(Max Heap):首先将待排序的序列构建成一个最大堆。从最后一个非叶子节点开始,依次将当...
    99+
    2023-10-26
    python
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作