堆

[lovelmh13]

概念

堆是一个完全二叉树

作用

堆可以快速找出最大值和最小值

常被用于**优先队列，**在优先级队列中，堆是最高效的数据结构

优先级队列：不是先进先出，而是优先级高的，先出

关键码

假定在数据记录中存在一个能够标识数据记录的数据项，并可依据该数据项对数据进行组织，则称此数据项为关键码（key）。

关节码不一定就是每个节点的值，它可能是一个对象，这里为了演示方便，才写了一个整数。实际应用中，可能是一个对象，用对象的某一个属性来做关键码。

如果有一个关键码集合K = {k0 , k1 , k2 , k3 , ... kn-1 } ，把它的所有元素按照完全二叉树的顺序存储方式存放在一个一维数组中，并且满足ki ≤ k2i+1 (左子女)且 ki ≤ k2i+2 (右子女)（或者 ki ≥ k2i+1 且 ki ≥ k2i+2） ,i = 0, 1,2, ... (n-2)/2,则称这个集合为最小堆(最大堆)。

在最小堆中，父节点的关键码小于等于它的左右子女的关键码，最大堆中，父节点的关键码大于等于左右子女的关键码。

数组存储

min_heap_arr = [9, 17, 65, 23, 45, 78, 87, 53, 31]

数组中的索引从0开始，元素个数为n, 在堆中给定索引为i的节点时：

• 如果i ≠ 0, 节点i是根节点，否则节点i的父节点为(i-1)/2
• 如果2i + 1 > n-1, 则节点i无左子女，否则节点i的左子女为2i + 1
• 如果2i + 2 > n-1, 则节点i无右子女，否则节点i的右子女为2i + 2

最小堆

最小堆的数组不一定是有序的，没有要求数组一定有序，只要每个节点的关键码，比左右子女小就可以

调整算法的基本思想

将一个堆调整为最小堆的方法：自下而上，先保证局部是一个最小堆，然后从局部到整体，逐步扩大，直到将整棵树都调整为最小堆

找到所有的分支节点，然后根据这些分支节点的索引从大到小依次进行调整，每次调整时，从该分支节点向下进行调整，使得这个分支节点和它的子孙节点构成一个最小堆，假设数组的大小为n，则最后一个分支节点的索引是（n-2）/2，第一个分支节点的索引是0。

在局部进行调整时，如果父节点的关键码小于等于两个子女中的最小关键码，说明，不需要调整了，否则，将父节点和拥有最小关键码的子女进行位置互换，并继续向下比较调整。

function MinHeap(arr) {
	// 传入一个数组,然后调整为最小堆
	this.init = function (arr) {
		max_size = arr.length;	// 堆的最大容量
		curr_size = max_size;
		heap = new Array(arr.length);
		// 填充heap, 目前还不是一个堆
		for (var i = 0; i < curr_size; i++) {
			heap[i] = arr[i];
		}
		var curr_pos = Math.floor((curr_size - 2) / 2);      // 这是堆的最后一个分支节点 (curr_size - 1 -1) / 2
		while (curr_pos >= 0) {
			shif_down(curr_pos, curr_size - 1);            // 局部自上向下下滑调整
			curr_pos -= 1;                               // 调整下一个分支节点
		}
	};
	/**
	* @params start number 当前的分支节点 
	* @params m number 数组最大的索引
	*/
	var shif_down = function (start, m) {
		// 从start这个位置开始,向下下滑调整
		var parent_index = start;                       // start就是当前这个局部的父节点
		var min_child_index = parent_index * 2 + 1;       // 因为一定有左孩子,先让min_child_index等于左孩子的索引
		while (min_child_index <= m) {
			// min_child_index+1 是左孩子的索引, 左孩子大于右孩子
			if (min_child_index < m && heap[min_child_index] > heap[min_child_index + 1]) {	// 左孩子比又孩子大
				min_child_index = min_child_index + 1;  // 让min_child_index指向右孩子；min_child_index永远指向值小的那个孩子
			}
			// 父节点的值小于等于两个孩子的最小值
			if (heap[parent_index] <= heap[min_child_index]) {
				break;   // 循环结束,不需要再调整了
			} else {
				// 父节点和子节点的值互换
				console.log(heap[parent_index]);
				debugger
				var tmp = heap[parent_index];
				heap[parent_index] = heap[min_child_index];
				heap[min_child_index] = tmp;
				parent_index = min_child_index; //这个parent_index是刚才换之前的那个索引，值已经调换了，现在也要把索引给变掉
				min_child_index = 2 * min_child_index + 1;	// 向下滑动，再换成左子节点，拿去对比，如果还有子节点，就再看一下这个新的局部，是否还是最小堆，这样就可以保证再换完节点以后，新的这个节点如果还比它的字节点大，就能继续向下去调换。最
				// 这里最后一句话，其实就是让每一次调换完，再去看下面有没有子节点，如果有，就再去比较一遍下面分部的节点，每次都把最小的放到这个布局的顶端来
			}
		}
	};
}

插入方法

insert方法，将新的元素插入到最小堆中，由于此前，最小堆已经建好，那么就可以从下向上，与父节点的关键码进行比较，对调。

不需要比较左右子节点的大小，因为已经是在最小堆中插入元素，所以父节点肯定比子节点都大，所以不需要跟兄弟比较。

注意，这个insert方法是一个一个插入，而不是先用了上面的Init方法，把数组变成最小堆再用这个。因为Init里面限制了curr_size = max_size;。

这个可以是不知道要有多少个元素的时候，一个一个插入。或者是已经是一个最小堆了，再插入。不要和init方法一起用

例如这么用：

var arr = [53, 17, 78, 9, 45, 65, 87, 23];
var min_heap = new MinHeap(8);

for(var i = 0; i<arr.length; i++){
    min_heap.insert(arr[i]);
}

删除堆的最小值（堆顶）

好玩儿的方法：把堆顶删掉，把最后一个节点放到堆顶。这样，只有index为0的那一小部分不是一个最小堆，我们只需要用shif_down对heap[0]，进行调整，变成最小堆就可以了。因为shif_down内部是自上向下进行调整的，会从上到下把一串儿都调整为新的最小堆的