`
dwljd
  • 浏览: 6095 次
  • 性别: Icon_minigender_1
  • 来自: 福建
最近访客 更多访客>>
社区版块
存档分类
最新评论

堆排序实现

阅读更多

前段时间在看侯捷的STL源码剖析,看到堆这一章顺带复习了一下堆排序,我们所说的堆一般指的是二叉堆,下面先来看下二叉堆的定义。

二叉堆定义

二叉堆是完全二叉树或是近似完全二叉树。

二叉堆满足两个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

 

最大堆父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。


存储

二叉堆一般用数组来表示。例如,根节点在数组中的位置是0,第n个位置节点的子节点位置在2n+1、2n+2。这种方式便于查找节点的子节点及父节点。如,位置0的子节点在1、2,位置1的子节点在3、4。

二叉堆插入

 

插入操作一般把数据插入到数组的最后面,然后,由此节点向上调整二叉堆,以满足二叉堆的性质。代码如下:

 

void push_heap(int array[], int hopeInd, int topInd, int value){
    int parent = (hopeInd - 1) / 2;
    while (hopeInd > topInd && array[parent] < value){
        array[hopeInd] = array[parent];
        hopeInd = parent;
        parent = (hopeInd - 1) / 2;
    }
    array[hopeInd] = value;
}

 

 

二叉堆删除

二叉堆的删除操作与插入相反,插入是“向上冒”,而删除时“向下沉”,即把根节点移除并把最后一个节点移到最前面,然后由此节点往下调整二叉堆。代码如下:

 

void fix_down_heap(int array[], int hopeInd, int size, int value){
    int secondChild = hopeInd * 2 + 2;
    int topInd = hopeInd;
    while (secondChild < size){
        if (array[secondChild-1] > array[secondChild]){
            secondChild--;
        }

        array[hopeInd] = array[secondChild];
        hopeInd = secondChild;
        secondChild = hopeInd * 2 + 2;
    }

    if (secondChild == size){
        array[hopeInd] = array[secondChild-1];
        hopeInd = secondChild - 1;
    }

    push_heap(array, hopeInd, topInd, value);
}

 

数组堆化

在进行二叉树排序之前,需要把数组转化为二叉堆,即数组堆化。由最后一个非子节点开始至根节点,一个个向下进行堆调整,即可完成堆的建立。建立堆的代码如下:

 

void make_heap(int array[], int size){
    int hopeInd = (size - 2) / 2;
    while (hopeInd >= 0){
        fix_down_heap(array, hopeInd, size, array[hopeInd]);
        hopeInd--;
    }
}

 

排序实现

对数组建立堆之后就可以进行排序操作了。根据二叉堆的性质,根节点是所有节点中值最大或最小的,因此堆排序就是一个不断删除根节点然后调整堆直到只有一个元素的过程。代码如下:

 

void swap(int& a, int& b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

 

void heapSort(int array[], int length){
    make_heap(array, length);

    for (int i=length-1; i>0; i--){
        swap(array[i], array[0]);
        fix_down_heap(array, 0, i, array[0]);
    }
}

至此,堆排序结束。

 

 

刚开始学习写博客,如有不足之处,欢迎指出。谢谢!

 

 

分享到:
评论

相关推荐

    C++堆排序实现算法

    简单的堆排序算法:以定长数组为例,动态数组等可以以此类推

    C语言堆排序实现优先序列

    根据给定的文件信息,我们可以总结出以下关于“C语言堆排序实现优先序列”的相关知识点: ### 一、堆排序的基本概念 堆排序是一种基于比较的排序算法,它利用二叉堆(通常为完全二叉树)的数据结构来实现。在本例...

    堆排序 c语言 演示

    #### 二、C语言中的堆排序实现 在本段代码中,作者通过C语言实现了堆排序的基本功能,并且提供了丰富的输出功能以便于观察排序过程。下面我们将对这段代码进行详细的解析: ##### 1. 函数定义 - **`build()`**:...

    堆排序的c++实现代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...

    学生成绩管理中实现堆排序

    在这个名为“学生成绩管理中实现堆排序”的项目中,我们看到一个C++编写的学生成绩管理系统,它使用了堆排序方法来管理并排序学生的成绩。 首先,让我们详细了解一下堆。堆通常是一个完全二叉树,可以分为最大堆和...

    堆排序实现c++代码和介绍实例

    ### 堆排序基本概念与实现 #### 一、堆排序简介 堆排序是一种基于比较的排序算法,它利用了一种特殊的完全二叉树结构——堆。堆是一种近似完全二叉树的数据结构,其中每个父节点的键值要么大于(大根堆)要么小于...

    完整详细版Python全套教学课件 第05节 堆排序实现.pdf

    完整详细版Python全套教学课件 第05节 堆排序实现.pdf

    数据结构排序 堆排序

    堆排序实现 以下是堆排序的实现代码: ```c void CreateHeap(int *arr, int nLength, int root) { if (!arr || nLength ) { return; } while (1) { if (root * 2 + 1 &gt; nLength - 1) { return; } // 如果...

    C++实现堆排序

    1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。

    用Java实现的堆排序算法

    用Java实现的堆排序算法,二叉树转换为堆,然后排序

    Python实现堆排序.rar

    本资源“Python实现堆排序.rar”提供了一个用Python语言编写的堆排序实现示例,通过分析这个代码,我们可以深入理解堆排序的工作原理以及如何在Python中实现它。 堆排序是一种基于比较的排序算法,其核心思想是利用...

    最小堆排序

    最小堆排序是一种基于比较的排序算法,其核心思想是利用数据结构中的“堆”来实现。在计算机科学中,堆通常被定义为一个完全二叉树,其中每个父节点的值都小于或等于其子节点的值,这样的堆称为最大堆;反之,如果每...

    C#堆排序实现方法

    堆排序是一种基于比较的排序算法,它通过...总的来说,C#中的堆排序实现利用了二叉堆的特性,通过构建和调整堆来实现高效的排序。这种算法在处理大数据集时具有较高的效率,但可能不是最优的选择,因为它不保证稳定性。

    c语言实现堆排序算法

    ### c语言实现堆排序算法 堆排序是一种基于比较的排序算法,它利用了二叉堆的数据结构特性来高效地对数据进行排序。堆排序可以分为最大堆和最小堆两种,其中最大堆指的是父节点的值总是大于或等于任意一个子节点的...

    排序算法编程 堆排序 快速排序

    堆排序通过构建和调整堆,然后交换堆顶元素与末尾元素来实现排序,直到整个序列变为有序。 接下来是快速排序,由C.A.R. Hoare在1960年提出,是目前最常用的内部排序算法之一。快速排序的核心思想是分治法:选取一个...

    堆排序算法实现堆排序

    堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆结构来实现数据的排序。在此,我们将深入探讨堆排序的基本概念、原理以及如何通过编程实现。 一、堆排序的概念 堆是一个近似完全二叉树的结构,...

    堆排序C++实现

    以下是一个基本的自定义堆排序实现: ```cpp #include void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left [left] &gt; arr[largest]) ...

    堆排序C语言实现

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在计算机科学中,堆通常被理解为一种特殊的完全二叉树,其中每个父节点的值都大于或等于(对于大顶堆)或小于或等于(对于小顶堆)其子...

    找出一个序列中前M个大值对应的索引(堆排序实现)

    堆排序是一种基于比较的排序算法,它利用了数据结构——堆(heap)的特性来实现高效排序。本篇文章将深入探讨如何使用堆排序算法找出一个序列中前M个大值对应的索引。 首先,让我们理解什么是堆。堆是一种特殊的树...

Global site tag (gtag.js) - Google Analytics