npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

@jayrbolton/heap

v0.0.1

Published

Heap data structures

Downloads

2

Readme

node-heap

Heap data structures for node & javascript

Heaps are useful for heap sort, priority queues, and other basic things. This supports min heaps, max heaps, and custom comparison functions.

This implementation uses a binary heap with a single flat array to store the tree.

Usage

var nodeHeap = require('node-heap')

var h = Heap.create([8, 0, 2, 6, 2, 9, 1, 5, 0])
h.findMax() // -> 9
h.insert(3)
h.isEmpty() // -> false
h.size() // -> 10
var root = h.pop() // -> 9
h.replace(10) // replace the root val with 10

console.log(h.indentFormat()) // -> prints an indentation-formatted tree of the heap

API

Heap.create(array, config)

Create a new heap from an unordered array. You can pass in custom compare and key functions with the config object. With custom key/compare functions, your array can contain any objects. With the default key and compare functions, it should be an array of numbers.

The config object can have these properties:

  • compare: custom comparison function -- defaults to number comparison (<, >, ===)
  • key: custom key function -- defaults to identity function
  • type: 'min' or 'max' -- defaults to 'max'

The compare function should take (x, y) and return 1 if x is greater, -1 if x is less, and 0 if they are equal.

The key function should take an element in the array as an arg and return the key for that elem -- eg. an 'id' property in an object.

Performance: O(n log n)

heap.findMax() or Heap.findMax(heap)

Get the maximum element (also the root element) in the heap. Does not affect the heap.

Can be either called as a method or a regular function.

heap.insert(val) or Heap.insert(val, heap)

Insert a new element into the heap. The heap will maintain its heap ordering.

Can be either called as a method or a regular function.

Performance is O(log n)

heap.merge(otherHeap) or Heap.merge(heap1, heap2)

Merge two heaps together into a single ordered heap.

Performance is O(n log n) -- this will be improved soon

heap.pop() or Heap.pop(heap)

Remove the root element of the heap.

Performance is O(n log n) -- this will be improved soon

heap.replace(val) or Heap.replace(val, heap)

Replace the root element of the heap.

Performance is O(log n)

heap.indentFormat(width) or Heap.indentFormat(heap, width)

Pretty print the heap tree as an indentation tree. Width is the optional number of spaces to indent -- deafults to 2

Misc functions

These are behind-the-scenes functions that are mostly useful for inserting or popping, but they are exposed in the API in case they are found useful for some reason.

heapify(heap)

Given a heap that might be totally unordered, order all the elements to obey the heap property. This is the main function used by Heap.create

Performance is O(n log n)

heap.siftUp(index) or Heap.siftUp(index, heap)

Given the index of the element in the heap array, put it in its correct place by traversing up the tree. This is used in heap.insert.

Can be either called as a method or a regular function.

heap.siftDown(index) or Heap.siftDown(index, heap)

Given the index of the element in the heap array, put it in its correct place by traversing down the tree. This is used in heapify.

Can be either called as a method or a regular function.

Heap.ileft(index), Heap.iright(index), Heap.iparent(index)

Given the heap array index of some element, get the left child index, right child index, or parent index for that element. O(1)

heap.left(index), Heap.left(index, heap), heap.right(index), Heap.right(index, heap), heap.parent(index), Heap.parent(index, heap)

Get the left-child value, right-child value, or the parent value for a given heap array elem index .

Install

With npm installed, run

$ npm install node-heap

License

MIT