fork(1) download
copy 
  1. // @file heap.js
  2. // @ingroup utility
  3. // Binary heap.
  4. // @date 05/22/2023
  5.  
  6. function Heap(compareFn) {
  7.     this._base = [];
  8.     this._comp = compareFn;
  9. }
  10.  
  11. Object.defineProperty(Heap.prototype, "size", {
  12.     get: function() {
  13.         return this._base.length;
  14.     }
  15. });
  16.  
  17. Object.defineProperty(Heap.prototype, "front", {
  18.     get: function() {
  19.         if (this._base.length === 0)
  20.             throw Error("Data access in empty heap");
  21.         return this._base[0];
  22.     }
  23. });
  24.  
  25. Heap.prototype.clear = function() {
  26.     this._base = [];
  27. };
  28.  
  29. Heap.prototype.push = function(value) {
  30.     let n = this._base.length;
  31.     let a = this._base;
  32.     heap_swim(a, 0, n, value, this._comp);
  33.     return this;
  34. };
  35.  
  36. Heap.prototype.pop = function() {
  37.     let n = this._base.length;
  38.     if (n === 0)
  39.         throw Error("Pop in empty heap");
  40.     let a = this._base;
  41.     let t = a[0];
  42.     heap_sink(a, 0, n-1, a[n-1], this._comp);
  43.     a.pop();
  44.     return t;
  45. };
  46.  
  47. Heap.prototype.make = function (iterable) {
  48.     this._base = Array.from(iterable);
  49.     let n = this._base.length;
  50.     let a = this._base;
  51.     for (let i = n>>1; i > 0; i--) {
  52.         heap_sink(a, i-1, n, a[i-1], this._comp);
  53.     }
  54.     return this;
  55. };
  56.  
  57. Heap.prototype.sorted = function () {
  58.     let n = this._base.length;
  59.     let a = this._base.slice();
  60.     for (let i = n-1; i > 0; i--) {
  61.         let t = a[i]; a[i] = a[0];
  62.         heap_sink(a, 0, i, t, this._comp);
  63.     }
  64.     return a;
  65. };
  66.  
  67. Heap.prototype.toString = function () {
  68.     return `Heap {${this._base.join(", ")}}`;
  69. };
  70.  
  71. // Private.
  72.  
  73. function heap_swim(base, h, i, key, comp) {
  74.     let hole = i;
  75.     while (i > h) {
  76.         i = (i-1)>>1; // Parent.
  77.         if (comp(key, base[i]) > 0)
  78.             base[hole] = base[i];
  79.         else
  80.             break;
  81.         hole = i;
  82.     }
  83.     base[hole] = key;
  84. }
  85.  
  86. function heap_sink(base, i, n, key, comp) {
  87.     let head = i;
  88.     let hole = i;
  89.     for (;;) {
  90.         i = (i+1)<<1; // Right child.
  91.         if (i > n)
  92.             break;
  93.         if (i === n || comp(base[i], base[i-1]) < 0)
  94.             i--;
  95.         base[hole] = base[i];
  96.         hole = i;
  97.     }
  98.     heap_swim(base, head, hole, key, comp);
  99. }
  100.  
  101. // Exports.
  102.  
  103. module.exports = Heap;
  104. // END
  105.  
  106.  
  107. // @file heap_test.js
  108. // @ingroup testing
  109. // Test Heap module.
  110.  
  111. // const Heap = require("heap");
  112. // const colorize = require("colorize");
  113. const colorize = (str, color) => str;
  114.  
  115. // Utility.
  116.  
  117. function report(condition, message) {
  118.     console.log(message.padEnd(30, ".")
  119.         + (condition
  120.             ? colorize("Pass", "green")
  121.             : colorize("Fail", "red")));
  122. }
  123.  
  124. function iota(n, start = 0, step = 1) {
  125.     return Array.from({length: n}, (_, i) => i*step + start);
  126. }
  127.  
  128. function shuffled(a) {
  129.     a = a.slice();
  130.     for (let n = a.length, i = 1; i < n; i++) {
  131.         let j = Math.random() * (i+1) | 0;
  132.         let temp = a[i]; a[i] = a[j]; a[j] = temp;
  133.     }
  134.     return a;
  135. }
  136.  
  137. function arrayEquals(a1, a2) {
  138.     if (a1.length !== a2.length)
  139.         return false;
  140.     return a1.every((v, i) => v === a2[i]);
  141. }
  142.  
  143. const maxHeapCompare = (a, b) => a - b;
  144. const minHeapCompare = (a, b) => b - a;
  145.  
  146. // Test.
  147.  
  148. function testConstructor() {
  149.     console.log(colorize("constructor", "blue"));
  150.  
  151.     let heap = new Heap(maxHeapCompare);
  152.  
  153.     report(heap.size === 0, "size");
  154.  
  155.     let except = false;
  156.  
  157.     try {
  158.         heap.front;
  159.     } catch (_) {
  160.         except = true;
  161.     }
  162.  
  163.     report(except, "exception (front)");
  164.  
  165.     except = false;
  166.  
  167.     try {
  168.         heap.pop();
  169.     } catch (_) {
  170.         except = true;
  171.     }
  172.  
  173.     report(except, "exception (pop)");
  174. }
  175.  
  176. function testPushMax() {
  177.     console.log(colorize("push(max)", "blue"));
  178.  
  179.     let keys = iota(10);
  180.     let heap = new Heap(maxHeapCompare);
  181.     let okay = true;
  182.  
  183.     for (const x of keys) {
  184.         heap.push(x);
  185.         if (heap.front !== x) {
  186.             okay = false;
  187.         }
  188.     }
  189.  
  190.     report(heap.size === keys.length, "size");
  191.     report(okay, "order");
  192.  
  193.     heap.clear();
  194.     okay = true;
  195.  
  196.     for (const x of keys.reverse()) {
  197.         heap.push(x);
  198.         if (heap.front !== 9) {
  199.             okay = false;
  200.         }
  201.     }
  202.  
  203.     report(heap.size === keys.length, "size  (rev)");
  204.     report(okay, "order (rev)");
  205. }
  206.  
  207. function testPushMin() {
  208.     console.log(colorize("push(min)", "blue"));
  209.  
  210.     let keys = iota(10);
  211.     let heap = new Heap(minHeapCompare);
  212.     let okay = true;
  213.  
  214.     for (const x of keys) {
  215.         heap.push(x);
  216.         if (heap.front !== 0) {
  217.             okay = false;
  218.         }
  219.     }
  220.  
  221.     report(heap.size === keys.length, "size");
  222.     report(okay, "order");
  223.  
  224.     heap.clear();
  225.     okay = true;
  226.  
  227.     for (const x of keys.reverse()) {
  228.         heap.push(x);
  229.         if (heap.front !== x) {
  230.             okay = false;
  231.         }
  232.     }
  233.  
  234.     report(heap.size === keys.length, "size  (rev)");
  235.     report(okay, "order (rev)");
  236. }
  237.  
  238. function testPop() {
  239.     console.log(colorize("pop", "blue"));
  240.  
  241.     let keys = shuffled(iota(10));
  242.     let heap = new Heap(minHeapCompare);
  243.  
  244.     for (const x of keys) {
  245.         heap.push(x);
  246.     }
  247.  
  248.     let sorted = [];
  249.  
  250.     for (; heap.size !== 0; heap.pop()) {
  251.         sorted.push(heap.front);
  252.     }
  253.  
  254.     report(sorted.length === keys.length, "size");
  255.  
  256.     keys.sort(maxHeapCompare);
  257.  
  258.     report(arrayEquals(sorted, keys), "order");
  259. }
  260.  
  261. function testMake() {
  262.     console.log(colorize("make", "blue"));
  263.  
  264.     let keys = shuffled(iota(10));
  265.     let heap = new Heap(minHeapCompare);
  266.  
  267.     heap.make(keys);
  268.  
  269.     report(heap.size === keys.length, "size");
  270.  
  271.     let sorted = [];
  272.  
  273.     for (; heap.size !== 0; heap.pop()) {
  274.         sorted.push(heap.front);
  275.     }
  276.  
  277.     keys.sort(maxHeapCompare);
  278.  
  279.     report(arrayEquals(sorted, keys), "order");
  280. }
  281.  
  282. function testSort() {
  283.     console.log(colorize("sort", "blue"));
  284.  
  285.     let keys = shuffled(iota(10));
  286.     let heap = new Heap(maxHeapCompare);
  287.  
  288.     heap.make(keys);
  289.  
  290.     let sorted = heap.sorted();
  291.  
  292.     report(sorted.length === keys.length, "size");
  293.  
  294.     keys.sort(maxHeapCompare);
  295.  
  296.     report(arrayEquals(sorted, keys), "order");
  297. }
  298.  
  299. function testClear() {
  300.     console.log(colorize("clear", "blue"));
  301.  
  302.     let keys = iota(10);
  303.     let heap = new Heap(maxHeapCompare);
  304.  
  305.     heap.make(keys);
  306.  
  307.     heap.clear();
  308.  
  309.     report(heap.size === 0, "size");
  310. }
  311.  
  312. // Entry.
  313.  
  314. testConstructor();
  315. testPushMax();
  316. testPushMin();
  317. testPop();
  318. testMake();
  319. testSort();
  320. testClear();
Success #stdin #stdout 0.06s 40804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
constructor
size..........................Pass
exception (front).............Pass
exception (pop)...............Pass
push(max)
size..........................Pass
order.........................Pass
size  (rev)...................Pass
order (rev)...................Pass
push(min)
size..........................Pass
order.........................Pass
size  (rev)...................Pass
order (rev)...................Pass
pop
size..........................Pass
order.........................Pass
make
size..........................Pass
order.........................Pass
sort
size..........................Pass
order.........................Pass
clear
size..........................Pass
https://ideone.com/s2EMBS
language:
Node.js (node 20.14)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!