MaxHeap implementation in JavaScript
up vote
1
down vote
favorite
Here is MaxHeap implementation in pure JavaScript:
/**
* We initialize index 0 because, calculations for finding
* children of a node and the parent of a node is easier
* parent = [ k/2 ], children: [ k*2, k*2+1 ]
*/
class Heap {
constructor() {
this.queue = [0];
};
/**
* Bottom-up reheapify (swim) : If the heap order is violated because a node's key
* becomes larger than that node's parents key, then we can make progress
* toward fixing the violation by exchanging the node with its parent
*
* @param {Number} k
*/
swim(k) {
while ( k>1 && this.less(k, Heap.flr(k/2)) ) {
this.exch(k, Heap.flr(k/2) ) ;
k = Heap.flr(k/2);
}
};
/**
* Top-down heapify (sink) : If the heap order is violated because a node's key becomes
* smaller than one or both of that node's children's keys, then we can make progress
* toward fixing the violation by exchanging the node with the larger of its two children.
*
* @param {Number} k
*/
sink(k) {
while ( 2*k <= this.n() ) {
const c1 = 2*k;
const c2 = 2*k + 1;
const j = this.more(c1,c2)?c2:c1;
if (this.more(k, j) ) {
this.exch(k, j);
} else {
break;
}
k = j;
}
};
/**
*
* @param {Number} i
* @param {Number} j
*/
less(i,j) {
return this.queue[i]>this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
more(i,j) {
return this.queue[i]<this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
exch(i, j) {
const tmp = this.queue[i];
this.queue[i] = this.queue[j];
this.queue[j] = tmp;
};
/**
* Inserts element into the internal queue
* @param {Number} k
*/
insert(k) {
this.queue.push(k);
this.swim(this.n());
};
/**
* Returns max element in the internal queue
*/
max() {
if (!this.isEmpty() ) {
return this.queue[1];
}
return false;
};
/**
* Deletes and returns max element from the internal queue
*/
delMax() {
if (!this.isEmpty()) {
const mx = this.queue[1];
this.queue[1] = this.queue.pop();
if (!this.isEmpty()) {
this.sink(1);
}
return mx;
};
return false;
};
/**
* Checks for emptyness (here we consider the queue empty if the length of the queue is 1)
*/
isEmpty() {
return this.queue.length === 1;
};
/**
* Returns last element index in the internal queue
*/
n() {
return this.queue.length-1;
};
/**
* in JS dividing odd number by even number gives fraction not integer,
* we need to get rid of this part
* @param {Number} i
*/
static flr(i) {
return Math.floor(i);
}
}
Is the implementation correct? What are the shortcomings that can be fixed?
javascript array heap
asked 52 mins ago
Humoyun
1235
add a comment |
up vote
1
down vote
favorite
Here is MaxHeap implementation in pure JavaScript:
/**
* We initialize index 0 because, calculations for finding
* children of a node and the parent of a node is easier
* parent = [ k/2 ], children: [ k*2, k*2+1 ]
*/
class Heap {
constructor() {
this.queue = [0];
};
/**
* Bottom-up reheapify (swim) : If the heap order is violated because a node's key
* becomes larger than that node's parents key, then we can make progress
* toward fixing the violation by exchanging the node with its parent
*
* @param {Number} k
*/
swim(k) {
while ( k>1 && this.less(k, Heap.flr(k/2)) ) {
this.exch(k, Heap.flr(k/2) ) ;
k = Heap.flr(k/2);
}
};
/**
* Top-down heapify (sink) : If the heap order is violated because a node's key becomes
* smaller than one or both of that node's children's keys, then we can make progress
* toward fixing the violation by exchanging the node with the larger of its two children.
*
* @param {Number} k
*/
sink(k) {
while ( 2*k <= this.n() ) {
const c1 = 2*k;
const c2 = 2*k + 1;
const j = this.more(c1,c2)?c2:c1;
if (this.more(k, j) ) {
this.exch(k, j);
} else {
break;
}
k = j;
}
};
/**
*
* @param {Number} i
* @param {Number} j
*/
less(i,j) {
return this.queue[i]>this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
more(i,j) {
return this.queue[i]<this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
exch(i, j) {
const tmp = this.queue[i];
this.queue[i] = this.queue[j];
this.queue[j] = tmp;
};
/**
* Inserts element into the internal queue
* @param {Number} k
*/
insert(k) {
this.queue.push(k);
this.swim(this.n());
};
/**
* Returns max element in the internal queue
*/
max() {
if (!this.isEmpty() ) {
return this.queue[1];
}
return false;
};
/**
* Deletes and returns max element from the internal queue
*/
delMax() {
if (!this.isEmpty()) {
const mx = this.queue[1];
this.queue[1] = this.queue.pop();
if (!this.isEmpty()) {
this.sink(1);
}
return mx;
};
return false;
};
/**
* Checks for emptyness (here we consider the queue empty if the length of the queue is 1)
*/
isEmpty() {
return this.queue.length === 1;
};
/**
* Returns last element index in the internal queue
*/
n() {
return this.queue.length-1;
};
/**
* in JS dividing odd number by even number gives fraction not integer,
* we need to get rid of this part
* @param {Number} i
*/
static flr(i) {
return Math.floor(i);
}
}
Is the implementation correct? What are the shortcomings that can be fixed?
javascript array heap
asked 52 mins ago
Humoyun
1235
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Here is MaxHeap implementation in pure JavaScript:
/**
* We initialize index 0 because, calculations for finding
* children of a node and the parent of a node is easier
* parent = [ k/2 ], children: [ k*2, k*2+1 ]
*/
class Heap {
constructor() {
this.queue = [0];
};
/**
* Bottom-up reheapify (swim) : If the heap order is violated because a node's key
* becomes larger than that node's parents key, then we can make progress
* toward fixing the violation by exchanging the node with its parent
*
* @param {Number} k
*/
swim(k) {
while ( k>1 && this.less(k, Heap.flr(k/2)) ) {
this.exch(k, Heap.flr(k/2) ) ;
k = Heap.flr(k/2);
}
};
/**
* Top-down heapify (sink) : If the heap order is violated because a node's key becomes
* smaller than one or both of that node's children's keys, then we can make progress
* toward fixing the violation by exchanging the node with the larger of its two children.
*
* @param {Number} k
*/
sink(k) {
while ( 2*k <= this.n() ) {
const c1 = 2*k;
const c2 = 2*k + 1;
const j = this.more(c1,c2)?c2:c1;
if (this.more(k, j) ) {
this.exch(k, j);
} else {
break;
}
k = j;
}
};
/**
*
* @param {Number} i
* @param {Number} j
*/
less(i,j) {
return this.queue[i]>this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
more(i,j) {
return this.queue[i]<this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
exch(i, j) {
const tmp = this.queue[i];
this.queue[i] = this.queue[j];
this.queue[j] = tmp;
};
/**
* Inserts element into the internal queue
* @param {Number} k
*/
insert(k) {
this.queue.push(k);
this.swim(this.n());
};
/**
* Returns max element in the internal queue
*/
max() {
if (!this.isEmpty() ) {
return this.queue[1];
}
return false;
};
/**
* Deletes and returns max element from the internal queue
*/
delMax() {
if (!this.isEmpty()) {
const mx = this.queue[1];
this.queue[1] = this.queue.pop();
if (!this.isEmpty()) {
this.sink(1);
}
return mx;
};
return false;
};
/**
* Checks for emptyness (here we consider the queue empty if the length of the queue is 1)
*/
isEmpty() {
return this.queue.length === 1;
};
/**
* Returns last element index in the internal queue
*/
n() {
return this.queue.length-1;
};
/**
* in JS dividing odd number by even number gives fraction not integer,
* we need to get rid of this part
* @param {Number} i
*/
static flr(i) {
return Math.floor(i);
}
}
Is the implementation correct? What are the shortcomings that can be fixed?
javascript array heap
asked 52 mins ago
Humoyun
1235
Here is MaxHeap implementation in pure JavaScript:
/**
* We initialize index 0 because, calculations for finding
* children of a node and the parent of a node is easier
* parent = [ k/2 ], children: [ k*2, k*2+1 ]
*/
class Heap {
constructor() {
this.queue = [0];
};
/**
* Bottom-up reheapify (swim) : If the heap order is violated because a node's key
* becomes larger than that node's parents key, then we can make progress
* toward fixing the violation by exchanging the node with its parent
*
* @param {Number} k
*/
swim(k) {
while ( k>1 && this.less(k, Heap.flr(k/2)) ) {
this.exch(k, Heap.flr(k/2) ) ;
k = Heap.flr(k/2);
}
};
/**
* Top-down heapify (sink) : If the heap order is violated because a node's key becomes
* smaller than one or both of that node's children's keys, then we can make progress
* toward fixing the violation by exchanging the node with the larger of its two children.
*
* @param {Number} k
*/
sink(k) {
while ( 2*k <= this.n() ) {
const c1 = 2*k;
const c2 = 2*k + 1;
const j = this.more(c1,c2)?c2:c1;
if (this.more(k, j) ) {
this.exch(k, j);
} else {
break;
}
k = j;
}
};
/**
*
* @param {Number} i
* @param {Number} j
*/
less(i,j) {
return this.queue[i]>this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
more(i,j) {
return this.queue[i]<this.queue[j];
};
/**
*
* @param {Number} i
* @param {Number} j
*/
exch(i, j) {
const tmp = this.queue[i];
this.queue[i] = this.queue[j];
this.queue[j] = tmp;
};
/**
* Inserts element into the internal queue
* @param {Number} k
*/
insert(k) {
this.queue.push(k);
this.swim(this.n());
};
/**
* Returns max element in the internal queue
*/
max() {
if (!this.isEmpty() ) {
return this.queue[1];
}
return false;
};
/**
* Deletes and returns max element from the internal queue
*/
delMax() {
if (!this.isEmpty()) {
const mx = this.queue[1];
this.queue[1] = this.queue.pop();
if (!this.isEmpty()) {
this.sink(1);
}
return mx;
};
return false;
};
/**
* Checks for emptyness (here we consider the queue empty if the length of the queue is 1)
*/
isEmpty() {
return this.queue.length === 1;
};
/**
* Returns last element index in the internal queue
*/
n() {
return this.queue.length-1;
};
/**
* in JS dividing odd number by even number gives fraction not integer,
* we need to get rid of this part
* @param {Number} i
*/
static flr(i) {
return Math.floor(i);
}
}
Is the implementation correct? What are the shortcomings that can be fixed?
javascript array heap
javascript array heap
asked 52 mins ago
Humoyun
1235
asked 52 mins ago
Humoyun
1235
asked 52 mins ago
Humoyun
1235
asked 52 mins ago
Humoyun
1235
asked 52 mins ago
Humoyun
1235
1235
add a comment |
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209769%2fmaxheap-implementation-in-javascript%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209769%2fmaxheap-implementation-in-javascript%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
