JS数据结构之堆
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。
大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
- JS 中通常用数组表示堆
- 左侧子节点的位置是 2*index + 1
- 右侧子节点的位置是 2*index + 2
- 父节点位置是 (index-1)/2
- 堆能高效、快速地找出最大值和最小值，时间复杂度：O(1)
- 找出第K个最大（最小）元素
堆排序:堆排序就是在前面的基础上，建堆，在一次删除堆顶元素就可以了，二叉堆本质上是一种完全二叉树，它分为两个类型，一个是最大堆，一个是最小堆。
《算法导论》上对堆排序讲得很详细。它把堆排序算法分成了三个子算法：一个将结点下沉的递归算法；一个初始建堆算法和一个排序算法。
Js实现最大堆
let heap = [];
function swap(index1, index2) {
let temp;
temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
function shiftup(index) {
let parentIndex = (index - 1) >> 1// Math.floor((index - 1) / 2);
if (index != 0 && heap[parentIndex] < heap[index]) { swap(parentIndex, index); shiftup(parentIndex); } } function shiftDown(index) { let leftNodeIndex = (index + 1) * 2 - 1, rightNodeIndex = (index + 1) * 2 if (leftNodeIndex < heap.length && heap[leftNodeIndex] > heap[index]) {
swap(leftNodeIndex, index);
shiftDown(leftNodeIndex);
} else if (rightNodeIndex < heap.length && heap[rightNodeIndex] > heap[index]) {
swap(rightNodeIndex, index);
shiftDown(rightNodeIndex);
}
}
function insert(val) {
heap.push(val);
shiftup(heap.length - 1);
}
function remove() {
swap(0, heap.length - 1);
heap.pop();
shiftDown(0);
return heap[0];
}
insert(1);
insert(3);
insert(2);
insert(5);
remove();
insert(4);
insert(6);
remove();
console.log(heap);//[ 4, 3, 2, 1 ]
Js实现堆排序: /* 排序思路：（降序）
* 将堆根保存于尾部，并对剩余序列调用调整函数，调整完成后，再将最大跟保存于尾部-1（-1，-2，...，-i），
* 再对剩余序列进行调整，反复进行该过程，直至排序完成。
*/
/* 将最大的元素调整到堆顶*/
function AdjustHeap(arr, pos, len){
var swap = arr[pos]; //保存当前节点
var child = pos * 2 + 1; //定位到当前节点的左边的子节点
while(child < len){ //递归遍历所有的子节点
//判断当前节点是否有右节点，若右节点较大，就采用右节点和当前节点进行比较
if(child + 1 < len && arr[child] < arr[child + 1]){
child += 1;
}
//比较当前节点和最大的子节点，小于就交换，交换后将当前节点定位到子节点上
if(arr[pos] < arr[child]){
arr[pos] = arr[child];
pos = child;
child = pos * 2 + 1;
}
else{
break;
}
arr[pos] = swap;
}
}
/* 构建堆：
* 满足：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子结点的关键字。
* 实现：从最后一个拥有子节点的节点开始，将该节点和其他节点进行比较，将最大的数交换给该节点，
* 交换后再依次向前节点进行相同的交换处理，直到构建出大顶堆。
*/
function BuildHeap(arr){
for(var i=arr.length/2; i>=0; i--){ //构建打顶堆
AdjustHeap(arr, i, arr.length);
}
}
/*堆排序算法*/
function HeapSort(arr){
BuildHeap(arr); //构建堆
for(var i=arr.length-1; i>0; i--){ //从数组的尾部进行调整
var swap = arr[i]; //堆顶永远是最大的元素,将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整
arr[i] = arr[0];
arr[0] = swap;
AdjustHeap(arr, 0, i); //将最大的元素进行调整，将最大的元素调整到堆顶
}
}
var arr = [46,12,33,72,68,19,80,33];
console.log('before: ' + arr);
HeapSort(arr);
console.log(' after: ' + arr); 
查看13道真题和解析