forked from mgechev/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheapsort.js
More file actions
93 lines (83 loc) · 2.53 KB
/
Copy pathheapsort.js
File metadata and controls
93 lines (83 loc) · 2.53 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
(function (exports) {
'use strict';
function comparator(a, b) {
return a - b;
}
var heapSort = (function () {
/**
* Finds the correct place of given element in given max heap.
*
* @private
* @param {Array} array Array.
* @param {Number} index Index of the element which palce in
* the max heap should be found.
* @param {Number} heapSize Size of the heap.
* @param {function} cmp Comparison function.
*/
function heapify(array, index, heapSize, cmp) {
var left = 2 * index + 1;
var right = 2 * index + 2;
var largest = index;
if (left < heapSize && cmp(array[left], array[index]) > 0) {
largest = left;
}
if (right < heapSize && cmp(array[right], array[largest]) > 0) {
largest = right;
}
if (largest !== index) {
var temp = array[index];
array[index] = array[largest];
array[largest] = temp;
heapify(array, largest, heapSize, cmp);
}
}
/**
* Builds max heap from given array.
*
* @private
* @param {Array} array Array which should be turned into max heap.
* @param {function} cmp Comparison function.
* @return {Array} array Array turned into max heap.
*/
function buildMaxHeap(array, cmp) {
for (var i = Math.floor(array.length / 2); i >= 0; i -= 1) {
heapify(array, i, array.length, cmp);
}
return array;
}
/**
* Heapsort. Turns the input array into max
* heap and after that sorts it.<br><br>
* Time complexity: O(N log N).
*
* @example
*
* var sort = require('path-to-algorithms/src' +
* '/sorting/heapsort').heapSort;
* console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
*
* @public
* @module sorting/heapsort
* @param {Array} array Input array.
* @param {Function} cmp Optional. A function that defines an
* alternative sort order. The function should return a negative,
* zero, or positive value, depending on the arguments.
* @return {Array} Sorted array.
*/
return function (array, cmp) {
cmp = cmp || comparator;
var size = array.length;
var temp;
buildMaxHeap(array, cmp);
for (var i = array.length - 1; i > 0; i -= 1) {
temp = array[0];
array[0] = array[i];
array[i] = temp;
size -= 1;
heapify(array, 0, size, cmp);
}
return array;
};
}());
exports.heapSort = heapSort;
})(typeof window === 'undefined' ? module.exports : window);