`
penergy
  • 浏览: 39877 次
社区版块
存档分类
最新评论

Heap Sort 实现(MIT Algorithm Course)

阅读更多
根据算法导论实现。有个小缺陷,heapsort中result是逆序排序。

def parent(i):
	return i%2;

def left(i):
	return 2*i+1;

def right(i):
	return 2*(i+1);

def maxHeapify(numList,i):
    l = left(i);
    r = right(i);
    if l<= len(numList)-1 and numList[l] > numList[i]:
        largest = l;
    else:
        largest = i;
    if r<= len(numList)-1 and numList[r] > numList[largest]:
        largest = r;
    if largest != i:
        numList[i], numList[largest] = numList[largest], numList[i]; #swap
        maxHeapify(numList,largest);

def buildMaxHeap(numList):
    heapsize = len(numList);
    for i in range(len(numList)//2-1,-1,-1):
        maxHeapify(numList,i);

def heapSort(numList):
    global alist;
    alist = numList;
    result= [];
    buildMaxHeap(alist);
    for i in range(len(alist)-1,0,-1):
        alist[0], alist[i] = alist[i], alist[0];
        #print(alist[i]);
        #print(i);
        result.append(alist.pop(i));
        maxHeapify(alist,0);
    result.append(alist.pop());
    return result;


从Stackoverflow找到的一种实现方式
def swap(i, j):                    
    sqc[i], sqc[j] = sqc[j], sqc[i] 

def heapify(end,i):   
    l=2 * i + 1  
    r=2 * (i + 1)   
    max=i   
    if l < end and sqc[i] < sqc[l]:   
        max = l   
    if r < end and sqc[max] < sqc[r]:   
        max = r   
    if max != i:   
        swap(i, max)   
        heapify(end, max)   

def heap_sort():     
    end = len(sqc)   
    start = end // 2 - 1 # use // instead of /
    for i in range(start, -1, -1):   
        heapify(end, i)   
    for i in range(end-1, 0, -1):   
        swap(i, 0)   
        heapify(i, 0)   

sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)






分享到:
评论

相关推荐

    Java heap Sort

    heap Sort. In briefly, it had been done with java.

    heap sort 的代码实现

    堆排序(Heap Sort)是一种基于比较的排序算法,它的核心思想是利用二叉堆的数据结构特性来实现排序。本文将详细介绍堆排序的实现步骤、重要概念以及相关操作。 首先,我们要理解什么是堆。堆是一种特殊的树形数据...

    pairing heap optimized dijkstra algorithm

    `heap.h`则是配对堆的实现,包括堆的创建、插入、删除和查找最小值等功能。 在实际应用中,配对堆优化的Dijkstra算法常被用于路由计算、网络流量分析、图形渲染等领域,尤其在需要频繁查询和更新最短路径的情况下,...

    code of heap sort

    it is a source code of heap sort ,so the number of words enough?

    test_heap_sort.rar_heap

    虽然堆排序可以手动实现,但VC++提供了标准模板库(STL),其中`&lt;algorithm&gt;`头文件包含了一些排序算法如`std::make_heap`、`std::push_heap`、`std::pop_heap`和`std::sort_heap`,这些可以简化堆排序的实现。...

    heap-sort code

    heap-sort code

    堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法

    堆排序 堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法

    SortAlgorithm.rar

    "SortAlgorithm.rar"这个压缩包很可能包含了多种经典的排序算法实现,主要针对的是Java编程语言。这里,我们将深入探讨几种常见的排序算法及其原理。 1. **冒泡排序**(Bubble Sort):冒泡排序是最基础的排序算法...

    maxheap-algorithm

    算法 这些包含以线性时间复杂度构建堆的 maxheap 和 minheap java 代码。 我们可以在堆上执行删除和插入功能。

    自己写的heap,C++实现

    本文将深入探讨由用户自编写的C++实现的小堆,以及与之相关的知识点。 首先,堆通常是一个完全二叉树,分为两种类型:大顶堆(最大堆)和小顶堆(最小堆)。在这个情况下,描述中提到的实现是小顶堆,意味着堆的根...

    C#,排列组合的堆生成法(Heap’s Algorithm for generating permutations)算法与源代码

    C#,排列组合的堆生成法(Heap’s Algorithm for generating permutations)算法与源代码 排列组合的堆生成法 堆生成算法用于生成n个对象的所有组合。其思想是通过选择一对要交换的元素,在不干扰其他n-2元素的情况...

    有向图的最短路径 源代码 Dijkstra's Shortest Path Algorithm 使用min heap

    本代码 利用 Dijkstra's Shortest Path Algorithm 求解有向图的最短路径。 包括 图的构建,求解过程的,排序使用的最小堆 等所有的源代码,并包括测试用例。 是学习最小堆 和 Dijkstra's Shortest Path Algorithm ...

    algorithm.zip

    heap_sort 56s: 56574ms: 56574802us shell_sort 71s: 71964ms: 71964163us radix_linklist_sort2 139s: 139973ms: 139973427us ./build/test_tools/sort_test -n 10000000 -d 7 quick_sort 1s: 1543ms: ...

    Heap:堆数据类型-matlab开发

    实现堆数据类型。 特性: h- 存储数据的数组heapSize- 堆的大小方法: Heap- Heap 类的构造函数,接受数字数组作为输入。 heapSort- 用于执行排序的方法,运行时间为 O(nlogn),尽管非常非常慢...不能用于对数组...

    AlgorithmMan by Iori(Heap Sort)

    AlgorithmMan by Iori,AlgorithmMan是使用Winform技术开发的一套用于算法演示的工具。 HeapSort为AlgorithmMan中的堆排序演示工具(这是可执行文件;需要.net 4.0支持;非源代码)。 原文:C#算法设计排序篇之06-堆...

    sort-algorithm_java.rar_sort_快速排序

    8. 堆排序(Heap Sort): 堆排序是一种树形选择排序,通过构造二叉堆进行排序。它可以视为选择排序的一种优化,因为它在原地排序数组,并且只需要O(1)的额外空间。堆排序的平均时间复杂度为O(n log n)。 以上各种...

    heapdump分析工具HeapAnalyzer

    heapdump分析工具------HeapAnalyzer: 2014年1月最新发布 用法: 在命令行执行 java -Xmx500m -jar ha453.jar

    sort_heap push_heap pop_heap 堆的各种算法

    最近在学习STL的源代码,看到这么多优秀的代码,心里痒痒的,于是自己实现了一遍,当然,有自己的特色,都是模块函数,稍稍用了一些traits特性。相互学习,呵呵

    数据结构常用算法c++实现

    Heap sort Double linked list Skip list Self-organized linked-list ops (move-to-front, move-ahead-one) Largest common sequence Binary search tree Dynamic order statistics Red-black tree Interval tree ...

    C#写的堆排序算法(heap sort)

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在C#中实现堆排序,我们可以分为两个主要步骤:建堆和调整堆。这里,我们将深入探讨堆排序的基本原理、C#实现的细节以及其在实际应用中的...

Global site tag (gtag.js) - Google Analytics