Skip to content

Instantly share code, notes, and snippets.

@xenowits
Last active May 8, 2021 16:45
Show Gist options
  • Save xenowits/0f46304fe63eaf2b1d65f588a87b11cd to your computer and use it in GitHub Desktop.
Save xenowits/0f46304fe63eaf2b1d65f588a87b11cd to your computer and use it in GitHub Desktop.
/** @class representing a binary heap node */
class Node {
/**
* @author: xenowits
* @param {string} id The accountID of the user
* @param {number} wt The associated weight (equal to noOfEntries)
* @param {number} totalWt Total weight of the subheap headed by current Node
*/
constructor(id, wt, totalWt) {
this.accountID = id;
this.wt = wt;
this.totalWt = totalWt;
}
}
/** @class representing a binary heap */
class BinaryHeap {
/**
* @author: xenowits
* @param {number} heapSize Initial size of the heap
*/
constructor(heapSize) {
// keeping first element as undefined to make the heap 1-indexed
this.heap = [undefined];
this.heapSize = heapSize;
}
/**
* Builds a heap from an array
* Healthy tip: Shuffle the array before building a heap
*
* @param {array} items Array of objects for building the heap
*/
buildHeap(items) {
items.forEach((ele) => {
let node = new Node(ele.id, ele.wt, ele.wt);
this.heap.push(node);
});
for (let i = this.heapSize; i > 1; i -= 1) {
// Add total weight of child to parent
this.heap[i >> 1].totalWt += this.heap[i].totalWt;
}
console.log(JSON.stringify(this.heap, null, 2));
}
/**
* Pops a random node from the heap
*/
popRandomNode() {
// Let's start with a random value of gas
var gas = this.heap[1].tw * Math.random();
var i = 1;
// Start driving at the root
// While we have enough gas to go past node i
while (gas > this.heap[i].wt) {
// console.log("iteration on step:", i);
gas -= this.heap[i].wt;
i = i << 1;
// Move to the first (left) child
// If we have enough gas, drive past first child and descendants
// And to the next child
if (gas > this.heap[i].totalWt) {
gas -= this.heap[i].totalWt;
i += 1;
}
}
// So heap[i] is our selected node
var accountID = this.heap[i].accountID;
console.log("Winner is ", accountID, " who has weight ", this.heap[i].wt);
var delta = this.heap[this.heapSize].wt - this.heap[i].wt;
// To make sure heap[i] is never chosen again,
// exchange last element of heap with heap[i]
this.heap[i].accountID = this.heap[this.heapSize].accountID;
this.heap[i].wt = this.heap[this.heapSize].wt;
this.heapSize -= 1;
// Also, propagate the new change up to the root
while (i > 0) {
this.heap[i].totalWt += delta;
i = i >> 1;
}
return accountID;
}
}
module.exports = BinaryHeap;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment