javascript 数据结构系列 (五) 堆
文章目录
博客说明
由于最近开始练习写作,文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除!
大家好,今天继续数据结构系列,今天讲的主题是堆,按照惯例不介绍概念性东西,其他文章介绍很多,主要从代码实现层次刨析,首先,实现堆构造函数
export default class Heap {
/**
* @constructs Heap
* @param {Function} [comparatorFunction]
*/
constructor(comparatorFunction) {
if (new.target === Heap) {
throw new TypeError("Cannot construct Heap instance directly");
}
// Array representation of the heap.
this.heapContainer = [];
this.compare = new Comparator(comparatorFunction);
}add 添加方法
/**
* @param {*} item
* @return {Heap}
*/
add(item) {
this.heapContainer.push(item);
this.heapifyUp();
return this;
}find 查找
/**
* @param {*} item
* @param {Comparator} [comparator]
* @return {Number[]}
*/
find(item, comparator = this.compare) {
const foundItemIndices = [];
for (
let itemIndex = 0;
itemIndex < this.heapContainer.length;
itemIndex += 1
) {
if (comparator.equal(item, this.heapContainer[itemIndex])) {
foundItemIndices.push(itemIndex);
}
}
return foundItemIndices;
}isEmpty 判断是否为空
/**
* @return {boolean}
*/
isEmpty() {
return !this.heapContainer.length;
}remove 删除方法
/**
* @param {*} item
* @param {Comparator} [comparator]
* @return {Heap}
*/
remove(item, comparator = this.compare) {
// Find number of items to remove.
const numberOfItemsToRemove = this.find(item, comparator).length;
for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
// We need to find item index to remove each time after removal since
// indices are being changed after each heapify process.
const indexToRemove = this.find(item, comparator).pop();
// If we need to remove last child in the heap then just remove it.
// There is no need to heapify the heap afterwards.
if (indexToRemove === this.heapContainer.length - 1) {
this.heapContainer.pop();
} else {
// Move last element in heap to the vacant (removed) position.
this.heapContainer[indexToRemove] = this.heapContainer.pop();
// Get parent.
const parentItem = this.parent(indexToRemove);
// If there is no parent or parent is in correct order with the node
// we're going to delete then heapify down. Otherwise heapify up.
if (
this.hasLeftChild(indexToRemove) &&
(!parentItem ||
this.pairIsInCorrectOrder(
parentItem,
this.heapContainer[indexToRemove]
))
) {
this.heapifyDown(indexToRemove);
} else {
this.heapifyUp(indexToRemove);
}
}
}
return this;
}
peek 方法
/**
* @return {*}
*/
peek() {
if (this.heapContainer.length === 0) {
return null;
}
return this.heapContainer[0];
}parent 获取父元素
/**
* @param {number} childIndex
* @return {*}
*/
parent(childIndex) {
return this.heapContainer[this.getParentIndex(childIndex)];
}leftchildren 获取左边节点
/**
* @param {number} parentIndex
* @return {*}
*/
leftChild(parentIndex) {
return this.heapContainer[this.getLeftChildIndex(parentIndex)];
}rightchildren 获取右边节点
/**
* @param {number} parentIndex
* @return {*}
*/
rightChild(parentIndex) {
return this.heapContainer[this.getRightChildIndex(parentIndex)];
}
toString 打印所有元素
/**
* @return {string}
*/
toString() {
return this.heapContainer.toString();
}以上就是堆简单实现,如果有不足指出欢迎反馈!
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论