根据算法导论实现。有个小缺陷,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)
分享到:
相关推荐
heap Sort. In briefly, it had been done with java.
堆排序(Heap Sort)是一种基于比较的排序算法,它的核心思想是利用二叉堆的数据结构特性来实现排序。本文将详细介绍堆排序的实现步骤、重要概念以及相关操作。 首先,我们要理解什么是堆。堆是一种特殊的树形数据...
`heap.h`则是配对堆的实现,包括堆的创建、插入、删除和查找最小值等功能。 在实际应用中,配对堆优化的Dijkstra算法常被用于路由计算、网络流量分析、图形渲染等领域,尤其在需要频繁查询和更新最短路径的情况下,...
it is a source code of heap sort ,so the number of words enough?
虽然堆排序可以手动实现,但VC++提供了标准模板库(STL),其中`<algorithm>`头文件包含了一些排序算法如`std::make_heap`、`std::push_heap`、`std::pop_heap`和`std::sort_heap`,这些可以简化堆排序的实现。...
heap-sort code
堆排序 堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法
"SortAlgorithm.rar"这个压缩包很可能包含了多种经典的排序算法实现,主要针对的是Java编程语言。这里,我们将深入探讨几种常见的排序算法及其原理。 1. **冒泡排序**(Bubble Sort):冒泡排序是最基础的排序算法...
算法 这些包含以线性时间复杂度构建堆的 maxheap 和 minheap java 代码。 我们可以在堆上执行删除和插入功能。
本文将深入探讨由用户自编写的C++实现的小堆,以及与之相关的知识点。 首先,堆通常是一个完全二叉树,分为两种类型:大顶堆(最大堆)和小顶堆(最小堆)。在这个情况下,描述中提到的实现是小顶堆,意味着堆的根...
C#,排列组合的堆生成法(Heap’s Algorithm for generating permutations)算法与源代码 排列组合的堆生成法 堆生成算法用于生成n个对象的所有组合。其思想是通过选择一对要交换的元素,在不干扰其他n-2元素的情况...
本代码 利用 Dijkstra's Shortest Path Algorithm 求解有向图的最短路径。 包括 图的构建,求解过程的,排序使用的最小堆 等所有的源代码,并包括测试用例。 是学习最小堆 和 Dijkstra's Shortest Path Algorithm ...
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: ...
实现堆数据类型。 特性: h- 存储数据的数组heapSize- 堆的大小方法: Heap- Heap 类的构造函数,接受数字数组作为输入。 heapSort- 用于执行排序的方法,运行时间为 O(nlogn),尽管非常非常慢...不能用于对数组...
AlgorithmMan by Iori,AlgorithmMan是使用Winform技术开发的一套用于算法演示的工具。 HeapSort为AlgorithmMan中的堆排序演示工具(这是可执行文件;需要.net 4.0支持;非源代码)。 原文:C#算法设计排序篇之06-堆...
8. 堆排序(Heap Sort): 堆排序是一种树形选择排序,通过构造二叉堆进行排序。它可以视为选择排序的一种优化,因为它在原地排序数组,并且只需要O(1)的额外空间。堆排序的平均时间复杂度为O(n log n)。 以上各种...
heapdump分析工具------HeapAnalyzer: 2014年1月最新发布 用法: 在命令行执行 java -Xmx500m -jar ha453.jar
最近在学习STL的源代码,看到这么多优秀的代码,心里痒痒的,于是自己实现了一遍,当然,有自己的特色,都是模块函数,稍稍用了一些traits特性。相互学习,呵呵
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#中实现堆排序,我们可以分为两个主要步骤:建堆和调整堆。这里,我们将深入探讨堆排序的基本原理、C#实现的细节以及其在实际应用中的...