hanyeah

（二叉）堆是一个数组。它可以看成一个近似的完全二叉树，树上的每一个节点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。表示堆得数组A包括两个属性，A.length给出数组元素的个数，A.heapSize表示有多少个堆元素存储在该数组中。

最大堆：父节点的值大于等于子节点的值。

最小堆：父节点的值小于等于子节点的值。

• MAX_HEAPIFY过程：时间复杂度是O(lgn)，它是维护堆性质的关键。

• BUILD-MAX_HEAP过程：线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆。

• HEAP-SORT过程：时间复杂度是O(nlgn)，功能是对一个数组进行原址排序。

• MAX_HEAP_INSERT，HEAP-EXTRACT-MAX，HEAP-INCRESE_KEY，HEAP-MAXIMUM过程：时间复杂度O(lgn)，功能是利用堆实现一个优先队列。

具体实现代码(最大堆)：

var a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
a.sort(function(){return Math.random()>0.5});
a.heapSize = a.length;

console.log(a.join('\t'));
//buildMaxHeap(a);
heapSort(a);
console.log(a.join('\t'));


function heapSort(a){
	buildMaxHeap(a);
	for(var i = a.length-1; i>0;i--){
		exchange(a, 0, i);
		a.heapSize--;
		maxHeapify(a, 0);
	}
}

function heapMaximum(a){
	return a[0];
}

function heapExtractMax(a){
	if(a.heapSize<0){
		throw(new Error('heap underflow'));
	}
	max = a[0];
	a[0] = a[a.heapSize - 1];
	a.heapSize--;
	maxHeapify(a, 0);
	return max;
}

function heapIncreaseKey(a, i, key){
	if(key < a[i]){
		throw(new Error('new key is smaller then current key'));
	}
	a[i] = key;
	var pi;
	while(i>0){
		pi = parent(i);
		if(a[pi] < a[i]){
			exchange(a, i, pi);
			i = pi;
		} else {
			break;
		}
	}
}

function maxHeapInsert(a, key){
	a[a.heapSize] = -Infinity;
	a.heapSize++;
	heapIncreaseKey(a, a.heapSize - 1, key);
}

function buildMaxHeap(a){
	for(var i = a.length>>1; i>=0;i--){
		maxHeapify(a, i);
	}
}

function buildMaxHeap2(a){
	a.heapSize = 1;
	for(var i = 1; i < a.length; i++){
		maxHeapInsert(a, a[i]);
	}
}

function heapDelete(a, i){
	a.heapSize--;
	a[i] = a[a.heapSize];
	maxHeapify(a, i);
	a[a.heapSize] = null;
}

function maxHeapify(a, i){
	var l = left(i);
	var r = right(i);
	var largest;
	if(l<a.heapSize && a[l]>a[i]){
		largest = l;
	} else {
		largest = i;
	}
	if(r<a.heapSize && a[r]>a[largest]){
		largest = r;
	}
	if(largest!=i){
		exchange(a,i,largest);
		maxHeapify(a,largest);
	}
}

function exchange(a,i,largest){
	var temp = a[i];
	a[i] = a[largest];
	a[largest] = temp;
}

function left(i){
	return i<<1 | 0x1;
}
function right(i){
	return (i<<1) + 2;
}

function parent(i){
	return (i-1)>>1;
}

/*function left(i){
	return i<<1;
}

function right(i){
	return i<<1 | 0x1;
}

function parent(i){
	return i>>1;
}*/

最小堆实现代码：

var a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
a.sort(function(){return Math.random()>0.5});
a.heapSize = a.length;

console.log(a.join('\t'));
//buildMaxHeap(a);
//heapSort(a);
console.log(a.join('\t'));


function heapSort(a){
	buildMinHeap(a);
	for(var i = a.length-1; i>0;i--){
		exchange(a, 0, i);
		a.heapSize--;
		minHeapify(a, 0);
	}
}

function heapMinimum(a){
	return a[0];
}

function heapExtractMin(a){
	if(a.heapSize<0){
		throw(new Error('heap underflow'));
	}
	min = a[0];
	a[0] = a[a.heapSize - 1];
	a.heapSize--;
	minHeapify(a, 0);
	return min;
}

function heapIncreaseKey(a, i, key){
	if(key > a[i]){
		throw(new Error('new key is bigger then current key'));
	}
	a[i] = key;
	var pi;
	while(i>0){
		pi = parent(i);
		if(a[pi] > a[i]){
			exchange(a, i, pi);
			i = pi;
		} else {
			break;
		}
	}
}

function minHeapInsert(a, key){
	a[a.heapSize] = Infinity;
	a.heapSize++;
	heapIncreaseKey(a, a.heapSize - 1, key);
}

function buildMinHeap(a){
	for(var i = a.length>>1; i>=0;i--){
		minHeapify(a, i);
	}
}

function buildMinHeap2(a){
	a.heapSize = 1;
	for(var i = 1; i < a.length; i++){
		minHeapInsert(a, a[i]);
	}
}

function heapDelete(a, i){
	a.heapSize--;
	a[i] = a[a.heapSize];
	minHeapify(a, i);
	a[a.heapSize] = null;
}

function minHeapify(a, i){
	var l = left(i);
	var r = right(i);
	var least;
	if(l<a.heapSize && a[l]<a[i]){
		least = l;
	} else {
		least = i;
	}
	if(r<a.heapSize && a[r]<a[least]){
		least = r;
	}
	if(least!=i){
		exchange(a,i,least);
		minHeapify(a,least);
	}
}

function exchange(a,i,least){
	var temp = a[i];
	a[i] = a[least];
	a[least] = temp;
}

function left(i){
	return i<<1 | 0x1;
}
function right(i){
	return (i<<1) + 2;
}

function parent(i){
	return (i-1)>>1;
}

/*function left(i){
	return i<<1;
}

function right(i){
	return i<<1 | 0x1;
}

function parent(i){
	return i>>1;
}*/

https://github.com/hanyeah/lianxi/tree/master/算法导论/6