brainwipe · November 19, 2014 21:19
diff --git a/gistfile1.html b/gistfile1.html
 <!DOCTYPE html><html><body>

 An implementation of Heap sort in javascript using an array as an underlying structure.<br/>
 Implemented to teach myself about heap sort and how it works, rather than a super fast implementation. Inspired by 
 <a href="http://www.algorist.com/">The Algorithm Design Manual</a>.
 Use the browser console (F12) to see the output.

 <script>
 var test_american_history_dates = [1492, 1783, 1776, 1804, 1865, 1945, 1963, 1918, 2001, 1941];

 function Heap() {};

 Heap.prototype.Items = [];
 Heap.prototype.LatestItemIndex = 0;

 Heap.prototype.Parent = function(index)
 {
 	if (index == 1)
 	{
 		return -1;
 	}
 	return Math.floor(index / 2);
 }

 Heap.prototype.YoungChild = function(index)
 {
 	return (2 * index);
 }

 Heap.prototype.Insert = function(item)
 {
 	this.LatestItemIndex = this.LatestItemIndex + 1;
 	this.Items[this.LatestItemIndex] = item;
 	this.BubbleUp(this.LatestItemIndex);
 }

 Heap.prototype.BubbleUp = function(index)
 {
 	var theParentIndex = this.Parent(index);

 	if (theParentIndex == -1)
 	{
 		return; // At top of heap, no parent
 	}
 	if (this.Items[theParentIndex] > this.Items[index])
 	{
 		this.Swap(theParentIndex, index);
 		this.BubbleUp(theParentIndex);
 	}
 }

 Heap.prototype.Swap = function(indexOne, indexTwo)
 {
 	var temp = this.Items[indexOne];
 	this.Items[indexOne] = this.Items[indexTwo];
 	this.Items[indexTwo] = temp;
 }

 Heap.prototype.ExtractMinimum = function()
 {
 	var minimumValue;
 	if (this.LatestItemIndex <= 0)
 	{
 		console.log('Heap empty');
 		return;
 	}
 	else
 	{
 		minimumValue = this.Items[1];
 		this.Items[1] = this.Items[this.LatestItemIndex];
 		this.Items.splice(this.LatestItemIndex, 1);
 		this.LatestItemIndex = this.LatestItemIndex - 1;
 		this.BubbleDown(1);
 	}
 	
 	return minimumValue;
 }

 // AKA Heapify
 Heap.prototype.BubbleDown = function(index)
 {
 	var childIndex = 0;
 	var i = 0;
 	var lightestChild  = 0;

 	childIndex = this.YoungChild(index);
 	lightestChild = index;

 	for (i=0; i<=1; i++)
 	{
 		if (childIndex + i <= this.LatestItemIndex)
 		{
 			if (this.Items[lightestChild] > this.Items[childIndex + i])
 			{
 				lightestChild = childIndex + i;
 			}
 		}
 	}

 	if (lightestChild != index)
 	{
 		this.Swap(index, lightestChild);
 		this.BubbleDown(lightestChild);
 	}
 }

 Heap.prototype.Make = function(items)
 {
 	for (var i=0; i < items.length; i++)
 	{
 		this.Insert(items[i]);
 	}
 }

 Heap.prototype.Sort = function(items)
 {
 	this.Make(items);
 	var	output = [];
 	var startingNumbers = this.LatestItemIndex;
 	for (var i=0; i < startingNumbers; i++)
 	{
 		output.push(this.ExtractMinimum());
 	}
 	return output;
 }

 var myMinHeap = new Heap();
 console.log("Unsorted dates: " + test_american_history_dates);
 var output = myMinHeap.Sort(test_american_history_dates);
 console.log(output);
 console.log(myMinHeap);

 </script>
 </body>
 </html>
	<!DOCTYPE html><html><body>

	An implementation of Heap sort in javascript using an array as an underlying structure.<br/>
	Implemented to teach myself about heap sort and how it works, rather than a super fast implementation. Inspired by
	<a href="http://www.algorist.com/">The Algorithm Design Manual</a>.
	Use the browser console (F12) to see the output.

	<script>
	var test_american_history_dates = [1492, 1783, 1776, 1804, 1865, 1945, 1963, 1918, 2001, 1941];

	function Heap() {};

	Heap.prototype.Items = [];
	Heap.prototype.LatestItemIndex = 0;

	Heap.prototype.Parent = function(index)
	{
	if (index == 1)
	{
	return -1;
	}
	return Math.floor(index / 2);
	}

	Heap.prototype.YoungChild = function(index)
	{
	return (2 * index);
	}

	Heap.prototype.Insert = function(item)
	{
	this.LatestItemIndex = this.LatestItemIndex + 1;
	this.Items[this.LatestItemIndex] = item;
	this.BubbleUp(this.LatestItemIndex);
	}

	Heap.prototype.BubbleUp = function(index)
	{
	var theParentIndex = this.Parent(index);

	if (theParentIndex == -1)
	{
	return; // At top of heap, no parent
	}
	if (this.Items[theParentIndex] > this.Items[index])
	{
	this.Swap(theParentIndex, index);
	this.BubbleUp(theParentIndex);
	}
	}

	Heap.prototype.Swap = function(indexOne, indexTwo)
	{
	var temp = this.Items[indexOne];
	this.Items[indexOne] = this.Items[indexTwo];
	this.Items[indexTwo] = temp;
	}

	Heap.prototype.ExtractMinimum = function()
	{
	var minimumValue;
	if (this.LatestItemIndex <= 0)
	{
	console.log('Heap empty');
	return;
	}
	else
	{
	minimumValue = this.Items[1];
	this.Items[1] = this.Items[this.LatestItemIndex];
	this.Items.splice(this.LatestItemIndex, 1);
	this.LatestItemIndex = this.LatestItemIndex - 1;
	this.BubbleDown(1);
	}

	return minimumValue;
	}

	// AKA Heapify
	Heap.prototype.BubbleDown = function(index)
	{
	var childIndex = 0;
	var i = 0;
	var lightestChild = 0;

	childIndex = this.YoungChild(index);
	lightestChild = index;

	for (i=0; i<=1; i++)
	{
	if (childIndex + i <= this.LatestItemIndex)
	{
	if (this.Items[lightestChild] > this.Items[childIndex + i])
	{
	lightestChild = childIndex + i;
	}
	}
	}

	if (lightestChild != index)
	{
	this.Swap(index, lightestChild);
	this.BubbleDown(lightestChild);
	}
	}

	Heap.prototype.Make = function(items)
	{
	for (var i=0; i < items.length; i++)
	{
	this.Insert(items[i]);
	}
	}

	Heap.prototype.Sort = function(items)
	{
	this.Make(items);
	var output = [];
	var startingNumbers = this.LatestItemIndex;
	for (var i=0; i < startingNumbers; i++)
	{
	output.push(this.ExtractMinimum());
	}
	return output;
	}

	var myMinHeap = new Heap();
	console.log("Unsorted dates: " + test_american_history_dates);
	var output = myMinHeap.Sort(test_american_history_dates);
	console.log(output);
	console.log(myMinHeap);

	</script>
	</body>
	</html>