思路
堆的操作：insert、poll、peek
-
insert: 先插入到最后一个节点，然后进行heapifyUp操作，这个过程会去比较当前节点的值与父节点的值，如果前者较大，会交换彼此的位置，并且更换index的位置为父节点的index，重复此过程，得到最大堆
-
poll: 删除最后一个节点，并且把根结点替换为刚才删除的节点。从上到下堆化，默认从根节点开始，看是否存在左右孩子节点，取出左右孩子节点较大值与父节点的数值比较，如果前者比较大，则需要替换两者的位置，更新index，重复此过程，得到删除一个元素的最大堆。
-
peek: 直接获取根节点的值
代码
function MaxHeap(capacity) {
// 容量
this.capacity = capacity;
this.array = [];
this.size = 0;
// 找到左孩子index
// 公式: 2*i+1
this.getLeftChildIndex = function(parentIndex) {
return 2*parentIndex+1;
}
// 找到右孩子index
// 公式: 2*i+2
this.getRightChildIndex = function(parentIndex) {
return 2*parentIndex+2;
}
// 找到父节点的index
this.getParentIndex = function(childIndex) {
return childIndex - 1 >> 1;
}
// 是否有左孩子
this.hasLeftChild = function(index) {
return this.getLeftChildIndex(index) < this.size;
};
// 是否有右孩子
this.hasRightChild = function(index) {
return this.getRightChildIndex(index) < this.size;
};
// 是否有父节点
this.hasParent = function(index) {
return this.getParentIndex(index) >= 0;
};
// 找到左孩子
this.leftChild = function(parentIndex) {
return this.array[this.getLeftChildIndex(parentIndex)];
}
// 找到右孩子
this.rightChild = function(parentIndex) {
return this.array[this.getRightChildIndex(parentIndex)];
};
// 找到父节点
this.parent = function(childIndex) {
return this.array[this.getParentIndex(childIndex)];
};
// 插入操作
// 步骤
// 1 在堆的最后新建一个节点
// 2 将数值赋予新节点
// 3 将其节点和父节点比较
// 4 如果新节点的数值比父节点大，交换父子节点的位置
// 5 重复步骤3和4直到最大堆的特性被满足
this.insert = function(val) {
this.array.push(val);
this.size++;
this.heapifyUp();
};
// 堆化（自底向上）
this.heapifyUp = function() {
// 找到最后一个节点
var index = this.size - 1;
// 有父节点且父节点的值小于当前节点的值，就要去交换两者位置，并把index置为父节点的index
while (this.hasParent(index) && this.parent(index) < this.array[index]) {
this.swap(this.array, this.getParentIndex(index), index);
index = this.getParentIndex(index);
}
}
// 交换数组的元素位置
this.swap = function(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 移出
// 步骤：
// 1 移除根节点
// 2 将最后的元素移到根节点处
// 3 将子节点和父节点比较
// 4 如果父节点的数值比较大子节点小，替换父子节点
// 5 重复步骤3和4直到最大堆的特性被满足
this.poll = function() {
if (this.size === 0) {
return null;
}
// 最后一个元素直接替换掉根节点
this.array[0] = this.array[this.size - 1];
this.size--;
this.heapifyDown();
};
// 堆化（自上而下）
this.heapifyDown = function() {
var index = 0;
while (this.hasLeftChild(index)) {
// 默认是左孩子的index大
var largestIndex = this.getLeftChildIndex(index);
// 比较左右孩子的值，较大值的index作为largestIndex的值
if (this.getRightChildIndex(index) && this.leftChild(index) < this.rightChild(index)) {
largestIndex = this.getRightChildIndex(index);
}
// 比较父节点的值与较大节点的值，如果父节点值小于较大节点的值，那么交换彼此的节点
if (this.array[index] < this.array[largestIndex]) {
this.swap(this.array, index, largestIndex);
} else {
break;
}
// 更新父节点的index
index = largestIndex;
}
}
this.peek = function() {
if (this.size === 0) {
return null;
}
return this.array[0];
}
}
复杂度分析
- 时间复杂度: O(logn)
- 空间复杂度: O(n)