Binary heap (Javascript)

From LiteratePrograms
Jump to: navigation, search
Other implementations: Javascript | Scheme

This program is a code dump.
Code dumps are articles with little or no documentation or rearrangement of code. Please help to turn it into a literate program. Also make sure that the source of this code does consent to release it under the CC0 license.

A binary heap is a simple concrete heap data structure using a binary tree. Binary heaps perform all operations in O(log n) time, except examining the root (minimum/maximum) element, which is constant time. They do not support a merge operation. They are often represented as complete binary trees stored implicitly in arrays; this representation is used in heapsort, for example.

Bla file

<<heap.js>>=
heapify

bla script summary

<<heapify>>=
	function heapify( ord_ar, disjoint )
	{
setup
insert
percolateUp
usage
	}
<<setup>>=
		var siz = ord_ar.length - 1;
		var heap = new Array( siz + 1 ); // min-heapify descending indicies
		var nonleaf = 0;
		heap = insertBunches( heap );
		// delete
		// peek
		// show
<<insert>>=
		function insert( heap, which ) // min heap
		{
			heap[ nonleaf ] = which;
			percolateUp( heap, nonleaf );
			nonleaf++;
			return heap;
		}
<<percolateUp>>=
		function percolateUp( heap, curr_i )
		{
			if ( curr_i == 0 )
				return; // else
			var par_i = h_parent( curr_i );
			if ( heap[curr_i] >= heap[par_i] )
				return // else:
			var temp = heap[ curr_i ]; // swap par & chi
			heap[ curr_i ] = heap[ par_i ];
			heap[ par_i ] = temp;
			curr_i = par_i;
			percolateUp( heap, curr_i );
		}
<<h_parent>>=
		function h_parent( child )
		{	return  Math.floor( (child + 1) / 2 ) - 1; }
<<usage>>=
		function insertBunches( heap )
		{
			// mix up insert for less obvious order
			var disj_lo = 15, disj_hi = 38;
			for ( ind = siz; ind > disj_hi; ind-- )
				insert( heap, ind );
			return heap
		}
Download code
hijacker
hijacker
hijacker
hijacker