🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more
Socket
Book a DemoInstallSign in
Socket

minheap

Package Overview
Dependencies
Maintainers
1
Versions
3
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

minheap

Simple implementation of min-heap

1.0.2
latest
Source
npm
Version published
Weekly downloads
9
-10%
Maintainers
1
Weekly downloads
 
Created
Source

A Simple Min Heap

This is a simple min heap implementation.

Install

Using npm

npm install minheap

API

Heap(compare)

Instantiate a heap using the compare function. If compare function is not given it falls back to a simple number comparison.

Required compare function should be similar to the function passed into Array.sort()

Heap.push(value)

Pushes the value to the heap

Heap.top()

Returns the value on top of the heap. This is the min value. If max value is required the compare function need to be altered accordingly.

Heap.pop()

Removes the top element from the heap and returns that value.

Example

Following example finds the Kth smallest number of a number list in O(NlogK) time. This is efficient compared to sorting entire list which takes O(NlogN) time, given that K << N.


 var Heap = require('minheap');
 // Max heap
 var heap = new Heap(function(a,b) {
  return b - a;
 });
 var N = 1<<20;
 var MAX_VAL = 1<<29;
 var K = 10
 var arr = [];

 // Generate random list
 for (var i=0; i<N; ++i) {
  arr[i] = Math.floor(Math.random() * MAX_VAL);
 }

 // Finding Kth smallest in O(N log K) using the heap
 for (var i=0; i<N; ++i) {
  if (i < K) {
   heap.push(arr[i]);
  } else {
   if (arr[i] < heap.top()) {
    heap.pop();
    heap.push(arr[i]);
   }
  }
 }

 console.log("10th smallest using heap: " + heap.top());

 // Finding Kth smallest in O(N log N) by sorting the entire list
 arr.sort(function(a,b) {
  return a - b;
 });
 console.log("10th smallest using sort: " + arr[K-1]);

Keywords

heap

FAQs

Package last updated on 05 Feb 2016

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts