Javascript 中的 HeapSort 实现
HeapSort implementation in Javascript
我正在学习堆,我想使用 MinHeap 在 Javascript 中实现堆排序算法。
问题是我一直得到一个未排序的数组。
我什至试图将一个工作算法从 C++ 翻译成 Javascript。
原始算法 link:https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/
C++:
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int smallest = i; // Initialize smalles as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr[i], arr[smallest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, smallest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
Javascipt(翻译代码):
function swap(arr, i, j){
const c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
function heapify(arr, n, i)
{
let smallest = i; // Initialize smalles as root
let l = 2 * i + 1; // left = 2*i + 1
let r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr[i], arr[smallest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, smallest);
}
}
// main function to do heap sort
function heapSort(arr, n)
{
// Build heap (rearrange array)
for (let i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (let i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
当我尝试使用这个数组 arr = [1,2,7,3,5] 时,heapSort 算法 returns 这个 table [ 1, 2, 7, 3, 5 ] ;
你能帮我弄清楚 JS 实现有什么问题吗?
提前谢谢你!
这段代码应该没问题:
const heapify = (arr, length, i) => {
let largest = i
const left = i * 2 + 1
const right = left + 1
if (left < length && arr[left] > arr[largest]) {
largest = left
}
if (right < length && arr[right] > arr[largest]) {
largest = right
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]
heapify(arr, length, largest)
}
return arr
}
const heapSort = arr => {
const length = arr.length
let i = Math.floor(length / 2 - 1)
let k = length - 1
while (i >= 0) {
heapify(arr, length, i)
i--
}
while (k >= 0) {
[arr[0], arr[k]] = [arr[k], arr[0]]
heapify(arr, k, 0)
k--
}
return arr
}
const arr = [4, 6, 3, 2, 9];
sortedArr = heapSort(arr);
console.log("Sorted array is \n", sortedArr)
我从here那里拿来的。如果您对它的实现方式更感兴趣,请查看 post。解释的很好。
更新
好的,关于你的代码,我看到了 2 个问题:
- 您错误地使用了“交换”功能。只需将
swap(arr[i], arr[smallest]
更改为 swap(arr, i, smallest)
; swap(arr[0], arr[i])
swap(arr, 0, i)
。此外,如果你想使用最新的 ES6 功能,你可以交换数组中的元素而无需实现“交换”功能,就像这样:[arr[0], arr[2]] = [arr[2], arr[0]]
(这会将位置 0 的元素与位置 2 的元素交换).这叫做destructuring assignment.
- 在“heapSort”函数的第一个 for 循环中,将 i 变量初始化为整数(注意 n / 2 可能是浮点数)。你可以这样做:
let i = Math.floor(n / 2 - 1)
.
这里我把固定代码留给你。我自己执行了它并且有效:
function swap(arr, i, j){
const c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
function heapify(arr, n, i)
{
let smallest = i; // Initialize smallest as root
let l = 2 * i + 1; // left = 2*i + 1
let r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr, i, smallest);
// Recursively heapify the affected sub-tree
heapify(arr, n, smallest);
}
}
// main function to do heap sort
function heapSort(arr, n)
{
// Build heap (rearrange array)
for (let i = Math.floor(n / 2 - 1); i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (let i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr, 0, i);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
const arr = [4, 6, 3, 2, 9];
heapSort(arr, arr.length);
console.log("Sorted array is \n", arr)
我正在学习堆,我想使用 MinHeap 在 Javascript 中实现堆排序算法。 问题是我一直得到一个未排序的数组。 我什至试图将一个工作算法从 C++ 翻译成 Javascript。 原始算法 link:https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/
C++:
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int smallest = i; // Initialize smalles as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr[i], arr[smallest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, smallest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
Javascipt(翻译代码):
function swap(arr, i, j){
const c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
function heapify(arr, n, i)
{
let smallest = i; // Initialize smalles as root
let l = 2 * i + 1; // left = 2*i + 1
let r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr[i], arr[smallest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, smallest);
}
}
// main function to do heap sort
function heapSort(arr, n)
{
// Build heap (rearrange array)
for (let i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (let i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
当我尝试使用这个数组 arr = [1,2,7,3,5] 时,heapSort 算法 returns 这个 table [ 1, 2, 7, 3, 5 ] ;
你能帮我弄清楚 JS 实现有什么问题吗? 提前谢谢你!
这段代码应该没问题:
const heapify = (arr, length, i) => {
let largest = i
const left = i * 2 + 1
const right = left + 1
if (left < length && arr[left] > arr[largest]) {
largest = left
}
if (right < length && arr[right] > arr[largest]) {
largest = right
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]
heapify(arr, length, largest)
}
return arr
}
const heapSort = arr => {
const length = arr.length
let i = Math.floor(length / 2 - 1)
let k = length - 1
while (i >= 0) {
heapify(arr, length, i)
i--
}
while (k >= 0) {
[arr[0], arr[k]] = [arr[k], arr[0]]
heapify(arr, k, 0)
k--
}
return arr
}
const arr = [4, 6, 3, 2, 9];
sortedArr = heapSort(arr);
console.log("Sorted array is \n", sortedArr)
我从here那里拿来的。如果您对它的实现方式更感兴趣,请查看 post。解释的很好。
更新
好的,关于你的代码,我看到了 2 个问题:
- 您错误地使用了“交换”功能。只需将
swap(arr[i], arr[smallest]
更改为swap(arr, i, smallest)
;swap(arr[0], arr[i])
swap(arr, 0, i)
。此外,如果你想使用最新的 ES6 功能,你可以交换数组中的元素而无需实现“交换”功能,就像这样:[arr[0], arr[2]] = [arr[2], arr[0]]
(这会将位置 0 的元素与位置 2 的元素交换).这叫做destructuring assignment. - 在“heapSort”函数的第一个 for 循环中,将 i 变量初始化为整数(注意 n / 2 可能是浮点数)。你可以这样做:
let i = Math.floor(n / 2 - 1)
.
这里我把固定代码留给你。我自己执行了它并且有效:
function swap(arr, i, j){
const c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
function heapify(arr, n, i)
{
let smallest = i; // Initialize smallest as root
let l = 2 * i + 1; // left = 2*i + 1
let r = 2 * i + 2; // right = 2*i + 2
// If left child is smaller than root
if (l < n && arr[l] < arr[smallest])
smallest = l;
// If right child is smaller than smallest so far
if (r < n && arr[r] < arr[smallest])
smallest = r;
// If smallest is not root
if (smallest != i) {
swap(arr, i, smallest);
// Recursively heapify the affected sub-tree
heapify(arr, n, smallest);
}
}
// main function to do heap sort
function heapSort(arr, n)
{
// Build heap (rearrange array)
for (let i = Math.floor(n / 2 - 1); i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (let i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr, 0, i);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
const arr = [4, 6, 3, 2, 9];
heapSort(arr, arr.length);
console.log("Sorted array is \n", arr)