`

heap sort

prototypeJavaScript数据结构XHTMLHTML 
阅读更多
heapsort

------
heap 数据结构

heap 是以 nearly complete binary tree 存储数据的，
tree height = lg(n+1),

max-heap:
      A[i] >= A[sub(i)]， 即 父节点 >= 子节点

------
heapsort 基本原理

首先将 heap 组装为 max-heap，则 root node 为最大值，
每组装1次 max-heap，就将 root node 取出放大结果数组中，
这样遍历 n-1 次后，就获得了已排序的数组，

------
heapsort 性能

时间复杂度： o(n*(lg n))
空间复杂度： o(n)

------
例子：

* javascript 
var arr_heap = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ];

/**
 * heapsort

 * 原理：采用 nealy complete binary tree 进行排序

 * 时间复杂度： o(n*(lg n)) , 空间复杂度： o(n)

 */
function HeapSort(arrInit) {
	this.arrInit = arrInit;
}

/** 根据 pos 获得 node，pos 从 1 开始 */
HeapSort.prototype.getNodeByPos = function(arr, pos) {
	return arr[pos - 1];
};
/** 根据 pos 设置 node，pos 从 1 开始 */
HeapSort.prototype.setNodeByPos = function(arr, pos, value) {
	return arr[pos - 1] = value;
};

/** 左 子节点的 位置，位置从 1 开始 */
HeapSort.prototype.leftPos = function(arr, pos) {
	var x = pos * 2;
	return x <= arr.length ? x : undefined;
};
/** 右 子节点的 位置 */
HeapSort.prototype.rightPos = function(arr, pos) {
	var x = pos * 2 + 1;
	return x <= arr.length ? x : undefined;
};
/** 父节点的 位置，位置从 1 开始 */
HeapSort.prototype.parent = function(pos) {
	return Math.floor(pos / 2);
};

/**
 * 单节点 max-heap 时，对 节点 和 子节点 位置执行的替换操作，并用返回值标识 if & which 位置改变了
 * 
 * @param arr
 * @param pos
 * @return 如果3个node已ok，则返回 -1，否则进行排序 并返回原来最大的位置
 */
HeapSort.prototype.maxHeapBasic = function(arr, pos) {
	var max = pos;
	var left = this.leftPos(arr, pos);
	var right = this.rightPos(arr, pos);
	if (left && this.getNodeByPos(arr, left) > this.getNodeByPos(arr, pos)) {
		max = left;
	}
	if (right && this.getNodeByPos(arr, right) > this.getNodeByPos(arr, max)) {
		max = right;
	}
	if (max == pos) {
		return -1;
	} else {
		var tmp = this.getNodeByPos(arr, pos);
		this.setNodeByPos(arr, pos, this.getNodeByPos(arr, max));
		this.setNodeByPos(arr, max, tmp);
		return max;
	}
};
/**
 * 由下而上构建 max-heap 时，对某节点执行 max-heap 操作
 * 
 * @param arr
 * @param pos
 *            节点位置，从1开始
 * @return
 */
HeapSort.prototype.maxHeap = function(arr, pos) {
	var max = pos;
	do {
		max = this.maxHeapBasic(arr, max);
	} while (max >= 1);
};
/**
 * 构建 max-heap
 * 
 * @param arr
 * @return
 */
HeapSort.prototype.buildMaxHeap = function(arr) {
	for ( var pos = Math.floor(arr.length / 2); pos >= 1; pos--) {
		this.maxHeap(arr, pos);
	}
};
/**
 * 排序
 * 
 * @return
 */
HeapSort.prototype.sort = function() {
	var result = new Array();
	// a copy of input array
	var arr = this.arrInit.slice();
	for ( var pos = arr.length; pos >= 2; pos--) {
		this.buildMaxHeap(arr); // 创建 max-heap，顶部是 当前剩余数组的 最大值
		result.unshift(arr.shift()); // 最大值写入 结果数组，并从原数组删除
	}
	result.unshift(arr.shift()); // 最后1个元素
	return result;
};


* html 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<script type="text/javascript" src="js/heap_sort.js"></script>
</head>
<body>
<input type="button" value="heap sort" onclick="alert(new HeapSort(arr_heap).sort());" />
</body>
</html>


------
分享到：
| merge sort
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Java heap Sort

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

    heap sort 的代码实现

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

    code of heap sort

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

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

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

    test_heap_sort.rar_heap

    标题中的“test_heap_sort.rar_heap”表明这是一个关于堆排序（Heap Sort）的程序实现，使用了VC++（Visual C++）编程语言。堆排序是一种基于比较的排序算法，它的核心思想是利用二叉堆的数据结构来对数组进行排序。...

    AlgorithmMan by Iori（Heap Sort）

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

    堆排序（Heap Sort）是一种基于比较的排序算法

    它的主要思想是将待排序的序列构造成一个大顶堆（或小顶堆），此时，整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（或最小值）。然后将剩余n-1个元素重新构造成一个...

    C#写的堆排序算法（heap sort）

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

    PHP排序算法之堆排序(Heap Sort)实例详解

    本文实例讲述了PHP排序算法之堆排序(Heap Sort)。分享给大家供大家参考，具体如下： 算法引进： 在这里我直接引用《大话数据结构》里面的开头： 在前面讲到 简单选择排序 ，它在待排序的 n 个记录中选择一个最小的...

    Insertion sorting，插入排序，c++

    插入排序（Insertion Sort）是一种简单直观的比较排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用...

    C语言中的sort

    - **堆排序（Heap Sort）**：利用二叉堆结构进行排序，时间复杂度为O(n log n)。 2. **在C语言中实现排序函数：** 实现这些排序算法时，你需要定义一个函数，接受一个指针数组和长度作为参数。例如，你可以创建一...

    python 实现 排序 课程设计 代码

    堆排序（Heap Sort） 插入排序（Insertion Sort） 引入排序（Intro Sort） 迭代归并排序（Iterative Merge Sort） 归并插入排序（Merge Insertion Sort） 归并排序（Merge Sort） 最高有效数字优先的基数排序（Msd ...

    heap-sort code

    heap-sort code

    图文详解Heap Sort堆排序算法及JavaScript的代码实现

    堆排序的主算法（Heap-Sort）首先将原始数组构建为最大堆，然后将堆顶元素（当前最大值）与末尾元素交换，这样末尾就得到了排序后的最大值。接着，对剩下的元素重新调整为最大堆，再将堆顶元素与末尾交换，如此反复...

    matlab开发-sort1m

    6. **堆排序（Heap Sort）**：利用堆这种数据结构实现的排序方法，效率较高，常用于大数据集。 7. **计数排序（Counting Sort）、桶排序（Bucket Sort）、基数排序（Radix Sort）**：这些是针对特定类型数据（如...

    sort.cpp_排序算法演示程序_

    6. **堆排序（Heap Sort）**：利用堆这种数据结构所设计的一种排序算法，能在O(n log n)的时间复杂度内完成排序。 7. **计数排序（Counting Sort）**：非基于比较的排序算法，适用于整数排序，尤其在数据范围不大的...

    经典算法的C#源码实现

    经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...

    常用的8个Python排序算法

    1. 冒泡排序（Bubble Sort） def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): ...7. 堆排序（Heap Sort） 8. 计数排序（Counting Sort） 解压密码 douge

    最大堆MaxHeap排序 C++代码

    最大堆排序（MaxHeap Sort）是一种基于比较的排序算法，它利用了数据结构中的最大堆特性来实现排序。最大堆是一种特殊的二叉堆，每个父节点的值都大于或等于其子节点的值，通常以数组的形式存储。下面将详细介绍最大...

    常用的十种java排序算法实现

    1. 冒泡排序（Bubble Sort） ...6.堆排序（Heap Sort） 7. 计数排序（Counting Sort） 8. 桶排序（Bucket Sort） 9. 基数排序（Radix Sort） 10. 希尔排序（Shell Sort） 解压密码 douge

Magicbox
Global site tag (gtag.js) - Google Analytics