堆排序(heapsort)

布满荆棘的人生 2023-10-09 10:32 60阅读 0赞

#### 堆排序(heapsort) ####

Heap Sort

1.  Complete Binary Tree
2.  parent > children

heapify

n = i ---> parent = (i - 1) / 2

----> c1 = 2i + 1

----> c2 = 2i + 2

#include <stdio.h>
    
    void swap(int arr[], int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    void heapify(int tree[], int n, int i) {
        if (i >= n) {
            return ;
        }
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && tree[c1] > tree[max]) {
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]) {
            max = c2;
        }
        if (max != i) {
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }
    
    void build_heap(int tree[], int n) {
        int last_node = n - 1;
        int parent = (last_node - 1) / 2;
        int i;
        for (i = parent; i >= 0; i--) {
            heapify(tree, n, i);
        }
    }
    
    void heap_sort(int tree[], int n) {
        build_heap(tree, n);
        int i;
        for (i = n - 1; i >= 0; i--) {
            swap(tree, i, 0);
            heapify(tree, i, 0);
        }
    }
    
    int main()
    {
        int tree[] = {2, 5, 3, 1, 10, 4};
        int n = 6;
        heap_sort(tree, n);
        int i;
        for (i = 0; i < n; i++) {
            printf("%d\n",tree[i]);
        }
        return 0;
    }
    
    /* !< output */
    1
    2
    3
    4
    5
    10

转载于:https://www.cnblogs.com/xuzhaoping/p/11493892.html

发表评论取消回复

表情：

评论列表（有 0 条评论，60人围观）

还没有评论，来说两句吧...

相关阅读

相关堆排序(heapsort)

堆排序(heapsort) Heap Sort 1. Complete Binary Tree 2. parent > children heapify n =

布满荆棘的人生/ 2023年10月09日 10:32/ 0 赞/ 61 阅读

相关算法-排序算法：堆排序（HeapSort ）【O(nlogn)】

MyArray.java / 数组 @author @version 2018/8/4 / publ

阳光穿透心脏的1/2处/ 2023年10月04日 12:30/ 0 赞/ 34 阅读

相关 FreeBSD中堆排序的实现heapsort

FreeBSD中堆排序的实现heapsort 源码：[https://github.com/freebsd/freebsd/blob/master/lib/libc/st

朴灿烈づ我的快乐病毒、/ 2023年06月19日 05:29/ 0 赞/ 2 阅读

相关 JavaScript实现heapsort堆排序算法（附完整源码）

JavaScript实现heapsort堆排序算法（附完整源码） Heap.js完整源代码 MinHeap.js完整源代码 Comparator.js完

蔚落/ 2022年09月07日 09:55/ 0 赞/ 196 阅读

相关【数据结构】中的堆(HeapSort)排序

堆排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序利用了大根堆(或小根堆)堆顶记录的关键

男娘i/ 2022年06月16日 11:44/ 0 赞/ 224 阅读

相关堆（heapsort）的有关概念

关于堆的一些基本概念 1. 堆：你可以把他看成是一个数组,近似的看成一个完全的二叉树，从二叉树顶端开始，从上到下，从左到右，按这个顺序的值组成了数组里的值。 2. 最

刺骨的言语ヽ痛彻心扉/ 2022年06月09日 04:25/ 0 赞/ 226 阅读

相关 Heapsort

堆排序：堆排序就是利用堆这种数据结构的性质来对数组进行排序，在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的性质可知，最大的值一定在堆顶。堆排序一种不稳定的排序算法

ゞ浴缸里的玫瑰/ 2022年06月02日 03:48/ 0 赞/ 136 阅读

相关排序算法7：堆排序（HeapSort）

排序算法7：堆排序（HeapSort）文章目录排序算法7：堆排序（HeapSort）前言 1. 算法步骤 2. 动图演示 2、实

淩亂°似流年/ 2021年09月28日 22:38/ 0 赞/ 404 阅读

相关排序-堆排序

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆：先看下图（来源

清疚/ 2021年09月20日 03:22/ 0 赞/ 466 阅读

相关选择排序之堆排序（HeapSort）

[图解排序算法(三)之堆排序][Link 1] 一、堆定义（二叉）堆是一个数组，类似于完全二叉树。分为两种形式： ![这里写图片描述][2016092622414

谁借莪１个温暖的怀抱￠/ 2021年06月10日 20:41/ 0 赞/ 501 阅读