前言
堆是一个特殊的树结构。
在前面的文章中，使用了二分搜索树实现了集合和映射这两个相对来讲更加高层的数据结构。树这种数据结构本身在计算机科学领域占有重要的地位，树这种形状本身可以产生非常多的拓展，在面对不同的问题的时候可以稍微改变或者限制树这种数据结构的性质，从而产生不同的数据结构，高效的解决不同的问题。
之后的文章会有四个不同的例子，堆、线段树、字典树、并查集，通过这些不同的数据结构的学习可以体会到数据结构的灵活之处，以及在设计数据结构的时候其中的一些思考非常重要，因为这些思考会让你对数据结构这个领域有更加深刻的认识。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
堆(Heap)
在计算机科学的领域通常你见到了O(logn)这样的时间复杂度。那么近乎一定就和树这样的数据结构有关，并不一定是显示的构造出一棵树，无论是排序算法中的归并排序、快速排序都是O(nlog(n))这个级别的，在排序的过程中没有使用树这种数据结构，但是这个递归的过程中其实形成了一棵隐形的递归树。
堆的基本结构
堆这种结构本身也是一棵树。其实堆也有很多种，堆最为主流的一种实现方式是使用二叉树来表示一个堆，也叫二叉堆(BinaryHeap)，说白了二叉堆就是满足一些特殊性质的二叉树。
满二叉树与完全二叉树。满二叉树，就是除了叶子节点之外，所有的节点的左右孩子都不为空。完全二叉树不一定是一个满的二叉树，但是它不满的那部分，也就是在缺失节点的那部分一定是在整颗树的右下侧。
也就是说把元素按照一层一层的顺序排列成一棵二叉树的形状的时候，得到的这棵树就是完全的二叉树。一个三层的满二叉树能装 7 个节点，一个四层的满二叉树能装 15 个节点，10 个节点对于一棵完全二叉树来说，前七节点装满前三层，对于第四层则是从左到右把剩下的三个节点放进去，这就是完全二叉树的定义。
不必拘泥于完全二叉树非常拗口的概念定义，其实完全二叉树非常的简单，就是把元素一层一层的放置，直到放不下了为止，所有整棵树的右下角的这部分可能是空的，因为缺少一些元素。
二叉堆满足的性质呢，首先它是一棵完全二叉树，除此之外它还有一个非常重要的性质，在堆(树)中的某个节点的值或者任意一个节点的值总是不大于其父节点的值。
也就是说所有节点的值一定大于或者等于它的孩子节点的值，所以根节点的元素一定是最大的元素，它大于它所有左右节点的值，同时它的左右子树也是一个堆，对于树中任意节点都会满足这个性质，这样得到的堆通常叫做最大堆。
因为根节点是最大的一个元素，相应的也可以定义出最小堆，这个定义方式和最大堆一样，只不过每一个节点的值都要小于等于它的孩子节点的值，这样得到的堆叫做最小堆。
最大堆和最小堆在某种程度上是可以统一的，因为什么叫大什么叫小可以自己来定义。
虽然在堆中每一个节点的值都大于等于它的左右孩子节点的值但是在堆这种数据结构上，层次比较低的节点的值不一定大于层次比较高的节点的值，因为二叉堆只保证每一个节点的父节点比自己大，但是节点的大小和节点所在的层次其实没有必然的联系。
实现二叉堆必须满足的要求，首先是完全二叉树，其次对于堆中每一个节点相应的元素值都是大于等于它的孩子节点的，这样得到的就是最大堆。
最大堆是一个完全二叉树，所以在具体实现上，有一个很巧妙的手段，可以使用二分搜索树的方式，先定义一个节点然后定义它的左右孩子就能实现这个堆了，但是完全二叉树的特点其实就是一个一个的节点按照顺序一层一层的码放出来。
可以使用数组的方式表现出一颗完全二叉树，对于数组的表示方式来说，要解决的问题是，在数组中的每一个节点应该怎么找到它的左右孩子，因为设置一个节点的话直接使用这个节点左右的指针去指向左右孩子所在的节点，但是用数组去存储的话，其实存在一些规律。
以数组的方式表现一棵完全二叉树的规律：parent(i) = i / 2，这个节点的父节点所在位置的索引就是当前节点二分之一(忽略小数或向下取整)，left child (i) = 2 * i，这个节点的左孩子所在位置的索引就是当前节点索引的 2 倍，right child (i) = 2 * i + 1。
这个节点的右孩子所在位置的索引就是当前节点索引的 2 倍+1，这样一来不仅可以非常方便的去索引这个节点的左右孩子，还可以非常方便的去索引到当前节点的父节点，这就是以数组的方式去表现一棵完全二叉树的规律和性质。
完全二叉树的好处，它本身就是那些元素按照顺序的一层一层的在这棵树中排列，所以将它标上索引之后，每一个节点和它的左右孩子节点以及它的父节点在索引之间就存在了一种很明显的逻辑关系，这个逻辑关系对于完全二叉树来说是成立的。
在很多教科书中实现堆的时候，用数组来存储，索引都是从 1 开始标，这是因为相对来说，计算孩子节点和父亲节点会比较方便。这样一来就会出现一个小问题，也就是将 0 这个位置空出来了，但是空出来并没有什么影响，例如在循环队列中、虚拟头节点链表中，也都诚心的空出这么一个位置来方便逻辑的编写。
不过对于堆来说，就算不空出这个位置，逻辑一样是非常简单的，区别在于计算父节点和左右孩子节点索引时相应的公式发生了一点点的改变，也就是相应的 i 进行了偏移。
// 原来是这样的 空了数组中索引为0的位置
parent(i) = i / 2
left child (i) = 2 * i
right child (i) = 2 * i + 1
// 偏移之后是这样的 没空数组中索引为0的位置
parent(i) = (i - 1) / 2
left child (i) = 2 * i + 1
right child (i) = 2 * i + 2实现最大堆基本架构
(class: Myarray, class: MaxHeap)
Myarray
// 自定义类
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MaxHeap
// 自定义二叉堆之最大堆
class MyMaxHeap {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
calcParentIndex(index) {
if (index === 0)
// 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
throw new Error("index is 0. doesn't have parent.");
return Math.floor((index - 1) / 2);
}
// 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
calcLeftChildIndex(index) {
return index * 2 + 1;
}
// 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
calcRightChildIndex(index) {
return index * 2 + 2;
}
// 获取堆中实际的元素个数
getSize() {
return this.myArray.getSize();
}
// 返回堆中元素是否为空的判断值
isEmpty() {
return this.myArray.isEmpty();
}
}向堆中添加元素 和 Sift Up
最大堆是一个完全二叉树，所以可以非常方便使用数组的方式来表示它。
向堆中添加元素，从用户的角度上来看是添加元素，但是从堆的角度上来看，会涉及到堆的一个非常基础的内部操作，也就是 Sift Up(堆中元素上浮的过程)。
添加操作一定是往堆的最底层进行添加，也就是向数组的尾部进行添加，新添加的元素会与其父祖节点进行比较，如果新添加的元素比父祖辈元素大，则会不断的交换元素，直到满足完全二叉树的性质。
也就是每一个节点都比其孩子节点大，也比其父节点小，这个不断交换元素，就是元素在堆中慢慢从底层上浮到合适层的过程就叫 Sift UP。计算父祖辈元素的索引可以通过新增加的元素的索引来进行计算，也就是数组中实际个数减去一获得。
SiftUp 操作无论是递归写法还是非递归写法，他们都一个共同的特点。元素上浮后结束的条件 当前节点元素值 小于其父节点元素值索引越界的终止条件 要上浮的元素索引 小于等于 0有了这两个条件之后，实现上浮操作很简单。
代码示例
(class: Myarray, class: MaxHeap)
Myarray
// 自定义类
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// 新增： 交换两个索引位置的变量 2018-11-6
swap(indexA, indexB) {
if (
indexA < 0 ||
indexA >= this.size ||
indexB < 0 ||
indexB >= this.size
)
throw new Error('Index is Illegal.'); // 索引越界异常
let temp = this.data[indexA];
this.data[indexA] = this.data[indexB];
this.data[indexB] = temp;
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MaxHeap
// 自定义二叉堆之最大堆
class MyMaxHeap {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 添加操作
add(element) {
// 追加元素
this.myArray.push(element);
// 将追加的元素上浮到堆中合适的位置
this.siftUp(this.myArray.getSize() - 1);
}
// 堆的上浮操作 -
siftUp(index) {
// this.nonRecursiveSiftUp(index);
this.recursiveSiftUp(index);
// 无论是递归还是非递归都有一个
// 元素上浮后结束的条件 当前节点元素值 小于其父节点元素值
// 和
// 索引即将越界的终止条件 要上浮的元素索引 小于等于0
}
// 堆的上浮操作 递归算法 -
recursiveSiftUp(index) {
// 解决最基本的问题， 递归终止条件
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
// 递归写法
if (this.compare(currentValue, parentValue) > 0) {
this.swap(index, parentIndex);
this.recursiveSiftUp(parentIndex);
}
}
// 堆的上浮操作 非递归算法 -
nonRecursiveSiftUp(index) {
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
while (this.compare(currentValue, parentValue) > 0) {
// 交换堆中两个元素位置的值
this.swap(index, parentIndex);
// 交换了位置之后，元素上浮后的索引变量也要进行相应的变更
index = parentIndex;
// 如果索引小于等于0了 那就结束循环
if (index <= 0) break;
currentValue = this.myArray.get(index);
parentIndex = this.calcParentIndex(index);
parentValue = this.myArray.get(parentIndex);
}
}
// 堆中两个元素的位置进行交换
swap(indexA, indexB) {
this.myArray.swap(indexA, indexB);
}
// 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
calcParentIndex(index) {
if (index === 0)
// 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
throw new Error("index is 0. doesn't have parent.");
return Math.floor((index - 1) / 2);
}
// 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
calcLeftChildIndex(index) {
return index * 2 + 1;
}
// 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
calcRightChildIndex(index) {
return index * 2 + 2;
}
// 比较的功能 -
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is error. element can't compare.");
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 获取堆中实际的元素个数
getSize() {
return this.myArray.getSize();
}
// 返回堆中元素是否为空的判断值
isEmpty() {
return this.myArray.isEmpty();
}
}取出堆中的最大元素和 Sift Down
从堆中取出元素也就是从堆的顶部取出元素。在最大堆中堆顶的元素就是最大元素，也就是堆中根节点的元素，这个过程叫做 Extract Max，也就是提取出堆中最大的元素。
从堆中取出元素，取出了堆顶的元素后，堆中就有两棵子树了，就不符合一棵完全二叉树的性质了，这时候就让最低层的最后一个元素放到最上层的根节点，那么又开始符合一棵完全二叉树的性质了。
只不过根节点的元素不一定符合父节点的值大于所有子节点的值的性质，也就是不符合堆的性质了，因为每一个节点要大于等于其孩子节点的值，那这个根节点就要进行下沉操作了。也就是每次下沉的时候都要去和它的两个孩子节点做比较，选择它的两个孩子中最大的那个元素。如果这两个孩子元素最大的那个元素比它自己还要大的话，那么它自己就和两个孩子中最大的那个元素交换一下位置，交换过位置之后如果还是不符合堆的性质，那么就继续下沉，继续交换，直到符合堆的性质为止。
因为那样就不需要再下沉了，这时候你需要手动的终止，如果你不手动的终止，虽然整个操作到最后也会结束，但是自动终止，时间复杂度一直都是最坏的情况O(logn)，其实手动终止，最好的情况是小于O(logn)的，所以如果可以的话尽量手动终止一下。
堆排序的基本原理，大概就是 Extract 这个过程，但是真正的堆排序还是有优化的空间的，现在的方式是将数据扔进一个堆，然后再从堆中一个一个取出来放入一个数组内，还使用了额外的空间，但是使用堆这种组织元素的思想完全可以将数据进行原地的排序。
在一个完全二叉树中，如果一个节点没有左孩子节点必然就没有右孩子节点。
代码示例
(class: Myarray, class: MaxHeap, class: Main)
Myarray
// 自定义类
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// 新增： 交换两个索引位置的变量 2018-11-6
swap(indexA, indexB) {
if (
indexA < 0 ||
indexA >= this.size ||
indexB < 0 ||
indexB >= this.size
)
throw new Error('Index is Illegal.'); // 索引越界异常
let temp = this.data[indexA];
this.data[indexA] = this.data[indexB];
this.data[indexB] = temp;
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MaxHeap
// 自定义二叉堆之最大堆
class MyMaxHeap {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 添加操作
add(element) {
// 追加元素
this.myArray.push(element);
// 将追加的元素上浮到堆中合适的位置
this.siftUp(this.myArray.getSize() - 1);
}
// 堆的上浮操作 -
siftUp(index) {
// this.nonRecursiveSiftUp(index);
this.recursiveSiftUp(index);
// 无论是递归还是非递归都有一个
// 元素上浮后结束的条件 当前节点元素值 小于其父节点元素值
// 和
// 索引即将越界的终止条件 要上浮的元素索引 小于等于0
}
// 堆的上浮操作 递归算法 -
recursiveSiftUp(index) {
// 解决最基本的问题， 递归终止条件
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
// 递归写法
if (this.compare(currentValue, parentValue) > 0) {
this.swap(index, parentIndex);
this.recursiveSiftUp(parentIndex);
}
}
// 堆的上浮操作 非递归算法 -
nonRecursiveSiftUp(index) {
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
while (this.compare(currentValue, parentValue) > 0) {
// 交换堆中两个元素位置的值
this.swap(index, parentIndex);
// 交换了位置之后，元素上浮后的索引变量也要进行相应的变更
index = parentIndex;
// 如果索引小于等于0了 那就结束循环
if (index <= 0) break;
currentValue = this.myArray.get(index);
parentIndex = this.calcParentIndex(index);
parentValue = this.myArray.get(parentIndex);
}
}
// 找到优先级最大的元素 （查找元素）操作
findMax() {
if (this.myArray.isEmpty())
throw new Error('can not findMax when heap is empty.');
return this.myArray.getFirst();
}
// 提取优先级最大的元素（删除元素）操作
extractMax() {
// 获取堆顶的元素
let maxElement = this.findMax();
// 获取堆底的元素
let element = this.myArray.getLast();
// 让堆底的元素替换掉堆顶的元素
this.myArray.set(0, element);
// 移除堆底的元素
this.myArray.pop();
// 让堆顶的元素开始下沉，从而能够正常满足堆的性质
this.siftDown(0);
// 返回堆顶的元素
return maxElement;
}
// 堆的下沉操作 -
siftDown(index) {
// this.nonRecursiveSiftDown(index);
this.recursiveSiftDown(index);
}
// 堆的下沉操作 递归算法 -
recursiveSiftDown(index) {
// 递归终止条件
// 如果当前索引位置的元素没有左孩子就说也没有右孩子，
// 那么可以直接终止，因为无法下沉
if (this.calcLeftChildIndex(index) >= this.myArray.getSize()) return;
const leftChildIndex = this.calcLeftChildIndex(index);
const leftChildValue = this.myArray.get(leftChildIndex);
const rightChildIndex = this.calcRightChildIndex(index);
let rightChildValue = null;
// let maxIndex = 0;
// if (rightChildIndex >= this.myArray.getSize())
// maxIndex = leftChildIndex;
// else {
// rightChildValue = this.myArray.get(rightChildIndex);
// if (this.compare(leftChildValue, rightChildValue) > 0)
// maxIndex = leftChildIndex;
// else
// maxIndex = rightChildIndex;
// }
// 这段代码是上面注释代码的优化
let maxIndex = leftChildIndex;
if (rightChildIndex < this.myArray.getSize()) {
rightChildValue = this.myArray.get(rightChildIndex);
if (this.compare(leftChildValue, rightChildValue) < 0)
maxIndex = rightChildIndex;
}
let maxValue = this.myArray.get(maxIndex);
let currentValue = this.myArray.get(index);
if (this.compare(maxValue, currentValue) > 0) {
// 交换位置
this.swap(maxIndex, index);
// 继续下沉
this.recursiveSiftDown(maxIndex);
}
}
// 堆的下沉操作 非递归算法 -
nonRecursiveSiftDown(index) {
// 该索引位置的元素有左右孩子节点才可以下沉，
// 在完全二叉树中 如果一个节点没有左孩子必然没有右孩子
while (this.calcLeftChildIndex(index) < this.myArray.getSize()) {
let leftChildIndex = this.calcLeftChildIndex(index);
let leftChildValue = this.myArray.get(leftChildIndex);
let rightChildIndex = this.calcRightChildIndex(index);
let rightChildValue = null;
let maxIndex = leftChildIndex;
if (rightChildIndex < this.myArray.getSize()) {
rightChildValue = this.myArray.get(rightChildIndex);
if (this.compare(leftChildValue, rightChildValue) <= 0)
maxIndex = rightChildIndex;
}
let maxValue = this.myArray.get(maxIndex);
let currentValue = this.myArray.get(index);
if (this.compare(maxValue, currentValue) > 0) {
this.swap(maxIndex, index);
index = maxIndex;
continue;
} else break;
}
}
// 堆中两个元素的位置进行交换
swap(indexA, indexB) {
this.myArray.swap(indexA, indexB);
}
// 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
calcParentIndex(index) {
if (index === 0)
// 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
throw new Error("index is 0. doesn't have parent.");
return Math.floor((index - 1) / 2);
}
// 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
calcLeftChildIndex(index) {
return index * 2 + 1;
}
// 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
calcRightChildIndex(index) {
return index * 2 + 2;
}
// 比较的功能 -
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is error. element can't compare.");
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 获取堆中实际的元素个数
size() {
return this.myArray.getSize();
}
// 返回堆中元素是否为空的判断值
isEmpty() {
return this.myArray.isEmpty();
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyMaxHeap Area');
const n = 100;
const maxHeap = new MyMaxHeap();
const random = Math.random;
// 循环添加随机数的值
for (let i = 0; i < n; i++) maxHeap.add(random() * n);
console.log('MaxHeap maxHeap size:' + maxHeap.size());
this.show('MaxHeap maxHeap size:' + maxHeap.size());
// 使用数组取值
let arr = [];
for (let i = 0; i < n; i++) arr[i] = maxHeap.extractMax();
console.log(
'Array arr size:' +
arr.length +
'，MaxHeap maxHeap size:' +
maxHeap.size()
);
this.show(
'Array arr size:' +
arr.length +
'，MaxHeap maxHeap size:' +
maxHeap.size()
);
console.log(arr, maxHeap);
// 检验一下是否符合要求
for (let i = 1; i < n; i++)
if (arr[i - 1] < arr[i]) throw new Error('error.');
console.log('test maxHeap completed.');
this.show('test maxHeap completed.');
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};堆的另外两个操作，Heapify 和 replace
从理论上讲这两个操作，可以使用之前堆中的操作来组合实现出来，但是这两个操作是比较常用的，而且可以通过对他们内部的实现来进行优化，所以不要使用组合原操作的方式来实现它。
replace
取出堆中最大元素之后，再放入一个新的元素。这个过程相当于是，堆中元素总数是没有变化的，这样的一个操作其实就是 extractMax 和 add，但是这会导致两次的O(logn)级别的操作。
由于整个过程中堆中的元素个数并没有发生改变，那么可以直接堆顶的元素替换成新的元素，替换成新的元素之后，这个新的元素有可能违背了堆的性质，那么直接进行 Sift Down 操作就可以了，那么就只是一次O(logn)级别的操作。
heapify
将任意的一个数组整理成堆的形状，由于堆是一棵完全二叉树，所以它可以直接用一个数组来表示。只要合理的交换数组中元素的位置，也可以将它整理成堆的形状。你可以先扫描一下当前的数组，将当前数组中所有的元素添加进这个堆所对应的对象中，其实也就完成了这个工作。
但是还有一个更加快速的方式，这个过程就叫做 Heapify，首先将当前数组看成一棵完全二叉树，虽然它目标并不太可能符合堆的性质，但是 对于这个完全二叉树，可以从最后一个非叶子节点开始进行 Sift Down 这个操作，也就是不断的进行下沉操作就可以了。从后往前不断的循环进行下沉操作，直到所有非叶子节点都符合堆的性质那就 ok 了。
定位最后一个非叶子节点所处的数组索引，一个很经典的面试题目，在计算机考试中出现过，就是用数组来表示一棵完全二叉树，那么它最后一个或者倒数第一个非叶子节点所对应的索引是多少。
这个问题其实非常简单，只需要拿到最后一个节点的索引，然后使用这个索引计算出它的父亲节点，如果起始索引是从 0 开始的，那就是这个最后一个节点的索引减去一之后再除以二取整即可，如果起始索引是从 1 开始的，那么就是这个最后一个节点的索引直接除以二再取整就好了。
heapify 原理：从倒数第一个非叶子节点向前一直遍历，遍历出到了第一个非叶子节点(根节点)，也就是对每一个节点都进行了下沉操作，然后整棵树就变成了最大堆。
这样一来就将一个普通的数组整理成了一个最大堆的形式，从一开始就抛弃了所有的叶子节点，那么几乎就抛弃了这棵二叉树中近一半的节点。剩下的一半的节点进行了 Sift Down 的操作，这比原来直接从一个空堆开始，一个一个添加元素的速度要快一点，因为每添加一个元素都会执行一次O(logn)级别的操作。
代码示例
(class: Myarray, class: MaxHeap, class: PerformanceTest, class: Main)
Myarray
// 自定义类
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// 新增： 交换两个索引位置的变量 2018-11-6
swap(indexA, indexB) {
if (
indexA < 0 ||
indexA >= this.size ||
indexB < 0 ||
indexB >= this.size
)
throw new Error('Index is Illegal.'); // 索引越界异常
let temp = this.data[indexA];
this.data[indexA] = this.data[indexB];
this.data[indexB] = temp;
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MaxHeap
// 自定义二叉堆之最大堆 Heap
class MyMaxHeap {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 添加操作
add(element) {
// 追加元素
this.myArray.push(element);
// 将追加的元素上浮到堆中合适的位置
this.siftUp(this.myArray.getSize() - 1);
}
// 堆的上浮操作 -
siftUp(index) {
this.nonRecursiveSiftUp(index);
// this.recursiveSiftUp(index);
// 无论是递归还是非递归都有一个
// 元素上浮后结束的条件 当前节点元素值 小于其父节点元素值
// 和
// 索引即将越界的终止条件 要上浮的元素索引 小于等于0
}
// 堆的上浮操作 递归算法 -
recursiveSiftUp(index) {
// 解决最基本的问题， 递归终止条件
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
// 递归写法
if (this.compare(currentValue, parentValue) > 0) {
this.swap(index, parentIndex);
this.recursiveSiftUp(parentIndex);
}
}
// 堆的上浮操作 非递归算法 -
nonRecursiveSiftUp(index) {
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
while (this.compare(currentValue, parentValue) > 0) {
// 交换堆中两个元素位置的值
this.swap(index, parentIndex);
// 交换了位置之后，元素上浮后的索引变量也要进行相应的变更
index = parentIndex;
// 如果索引小于等于0了 那就结束循环
if (index <= 0) break;
currentValue = this.myArray.get(index);
parentIndex = this.calcParentIndex(index);
parentValue = this.myArray.get(parentIndex);
}
}
// 找到优先级最大的元素 （查找元素）操作
findMax() {
if (this.myArray.isEmpty())
throw new Error('can not findMax when heap is empty.');
return this.myArray.getFirst();
}
// 提取优先级最大的元素（删除元素）操作
extractMax() {
// 获取堆顶的元素
let maxElement = this.findMax();
// 获取堆底的元素
let element = this.myArray.getLast();
// 让堆底的元素替换掉堆顶的元素
this.myArray.set(0, element);
// 移除堆底的元素
this.myArray.pop();
// 让堆顶的元素开始下沉，从而能够正常满足堆的性质
this.siftDown(0);
// 返回堆顶的元素
return maxElement;
}
// 堆的下沉操作 -
siftDown(index) {
this.nonRecursiveSiftDown(index);
// this.recursiveSiftDown(index);
}
// 堆的下沉操作 递归算法
recursiveSiftDown(index) {
// 递归终止条件
// 如果当前索引位置的元素没有左孩子就说也没有右孩子，
// 那么可以直接终止，因为无法下沉
if (this.calcLeftChildIndex(index) >= this.myArray.getSize()) return;
let leftChildIndex = this.calcLeftChildIndex(index);
let leftChildValue = this.myArray.get(leftChildIndex);
let rightChildIndex = this.calcRightChildIndex(index);
let rightChildValue = null;
// let maxIndex = 0;
// if (rightChildIndex >= this.myArray.getSize())
// maxIndex = leftChildIndex;
// else {
// rightChildValue = this.myArray.get(rightChildIndex);
// if (this.compare(rightChildValue, leftChildValue) > 0)
// maxIndex = rightChildIndex;
// else
// maxIndex = leftChildIndex;
// }
// 这段代码是上面注释代码的优化
let maxIndex = leftChildIndex;
if (rightChildIndex < this.myArray.getSize()) {
rightChildValue = this.myArray.get(rightChildIndex);
if (this.compare(leftChildValue, rightChildValue) < 0)
maxIndex = rightChildIndex;
}
let maxValue = this.myArray.get(maxIndex);
let currentValue = this.myArray.get(index);
if (this.compare(maxValue, currentValue) > 0) {
// 交换位置
this.swap(maxIndex, index);
// 继续下沉
this.recursiveSiftDown(maxIndex);
}
}
// 堆的下沉操作 非递归算法 -
nonRecursiveSiftDown(index) {
// 该索引位置的元素有左右孩子节点才可以下沉，
// 在完全二叉树中 如果一个节点没有左孩子必然没有右孩子
while (this.calcLeftChildIndex(index) < this.myArray.getSize()) {
let leftChildIndex = this.calcLeftChildIndex(index);
let leftChildValue = this.myArray.get(leftChildIndex);
let rightChildIndex = this.calcRightChildIndex(index);
let rightChildValue = null;
let maxIndex = leftChildIndex;
if (rightChildIndex < this.myArray.getSize()) {
rightChildValue = this.myArray.get(rightChildIndex);
if (this.compare(leftChildValue, rightChildValue) < 0)
maxIndex = rightChildIndex;
}
let maxValue = this.myArray.get(maxIndex);
let currentValue = this.myArray.get(index);
if (this.compare(maxValue, currentValue) > 0) {
this.swap(maxIndex, index);
index = maxIndex;
continue;
} else break;
}
}
// 将堆顶的元素用一个新元素替换出来
replace(element) {
let maxElement = this.findMax();
this.myArray.set(0, element);
this.siftDown(0);
return maxElement;
}
// 将一个数组变成一个最大堆 -
heapify(array) {
// 将数组中的元素添加到自定义动态数组里
for (const element of array) this.myArray.push(element);
// 减少一个O(n)的操作，不然性能相对来说会差一些
// this.myArray.data = array;
// this.myArray.size = array.length;
// 这个动态数组满足了一棵完全二叉树的性质
// 获取 这棵完全二叉树 最后一个非叶子节点的索引
let index = this.calcParentIndex(this.myArray.getSize() - 1);
// 从最后一个非叶子节点开始遍历 从后向前遍历 不停的下沉， 这个就是heapify的过程
// for (let i = index; i >= 0; i --) { this.siftDown(i);}
while (0 <= index) this.siftDown(index--);
}
// 堆中两个元素的位置进行交换
swap(indexA, indexB) {
this.myArray.swap(indexA, indexB);
}
// 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
calcParentIndex(index) {
if (index === 0)
// 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
throw new Error("index is 0. doesn't have parent.");
return Math.floor((index - 1) / 2);
}
// 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
calcLeftChildIndex(index) {
return index * 2 + 1;
}
// 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
calcRightChildIndex(index) {
return index * 2 + 2;
}
// 比较的功能 -
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is error. element can't compare.");
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 获取堆中实际的元素个数
size() {
return this.myArray.getSize();
}
// 返回堆中元素是否为空的判断值
isEmpty() {
return this.myArray.isEmpty();
}
}PerformanceTest
// 性能测试
class PerformanceTest {
constructor() {}
// 对比队列
testQueue(queue, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
queue.enqueue(random() * openCount);
}
while (!queue.isEmpty()) {
queue.dequeue();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比栈
testStack(stack, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
stack.push(random() * openCount);
}
while (!stack.isEmpty()) {
stack.pop();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比集合
testSet(set, openCount) {
let startTime = Date.now();
let random = Math.random;
let arr = [];
let temp = null;
// 第一遍测试
for (var i = 0; i < openCount; i++) {
temp = random();
// 添加重复元素，从而测试集合去重的能力
set.add(temp * openCount);
set.add(temp * openCount);
arr.push(temp * openCount);
}
for (var i = 0; i < openCount; i++) {
set.remove(arr[i]);
}
// 第二遍测试
for (var i = 0; i < openCount; i++) {
set.add(arr[i]);
set.add(arr[i]);
}
while (!set.isEmpty()) {
set.remove(arr[set.getSize() - 1]);
}
let endTime = Date.now();
// 求出两次测试的平均时间
let avgTime = Math.ceil((endTime - startTime) / 2);
return this.calcTime(avgTime);
}
// 对比映射
testMap(map, openCount) {
let startTime = Date.now();
let array = new MyArray();
let random = Math.random;
let temp = null;
let result = null;
for (var i = 0; i < openCount; i++) {
temp = random();
result = openCount * temp;
array.add(result);
array.add(result);
array.add(result);
array.add(result);
}
for (var i = 0; i < array.getSize(); i++) {
result = array.get(i);
if (map.contains(result)) map.add(result, map.get(result) + 1);
else map.add(result, 1);
}
for (var i = 0; i < array.getSize(); i++) {
result = array.get(i);
map.remove(result);
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比堆 主要对比 使用heapify 与 不使用heapify时的性能
testHeap(heap, array, isHeapify) {
const startTime = Date.now();
// 是否支持 heapify
if (isHeapify) heap.heapify(array);
else {
for (const element of array) heap.add(element);
}
console.log('heap size:' + heap.size() + '\r\n');
document.body.innerHTML += 'heap size:' + heap.size() + '<br /><br />';
// 使用数组取值
let arr = new Array(heap.size());
for (let i = 0; i < arr.length; i++) arr[i] = heap.extractMax();
console.log(
'Array size:' + arr.length + '，heap size:' + heap.size() + '\r\n'
);
document.body.innerHTML +=
'Array size:' +
arr.length +
'，heap size:' +
heap.size() +
'<br /><br />';
// 检验一下是否符合要求
for (let i = 1; i < arr.length; i++)
if (arr[i - 1] < arr[i]) throw new Error('error.');
console.log('test heap completed.' + '\r\n');
document.body.innerHTML += 'test heap completed.' + '<br /><br />';
const endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
calcTime(result) {
//获取距离的天数
var day = Math.floor(result / (24 * 60 * 60 * 1000));
//获取距离的小时数
var hours = Math.floor((result / (60 * 60 * 1000)) % 24);
//获取距离的分钟数
var minutes = Math.floor((result / (60 * 1000)) % 60);
//获取距离的秒数
var seconds = Math.floor((result / 1000) % 60);
//获取距离的毫秒数
var milliSeconds = Math.floor(result % 1000);
// 计算时间
day = day < 10 ? '0' + day : day;
hours = hours < 10 ? '0' + hours : hours;
minutes = minutes < 10 ? '0' + minutes : minutes;
seconds = seconds < 10 ? '0' + seconds : seconds;
milliSeconds =
milliSeconds < 100
? milliSeconds < 10
? '00' + milliSeconds
: '0' + milliSeconds
: milliSeconds;
// 输出耗时字符串
result =
day +
'天' +
hours +
'小时' +
minutes +
'分' +
seconds +
'秒' +
milliSeconds +
'毫秒' +
' <<<<============>>>> 总毫秒数：' +
result;
return result;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MaxHeap Comparison Area');
const n = 1000000;
const maxHeapIsHeapify = new MyMaxHeap();
const maxHeapNotHeapify = new MyMaxHeap();
let performanceTest1 = new PerformanceTest();
const random = Math.random;
let arr = [];
let arr1 = [];
// 循环添加随机数的值
for (let i = 0; i < n; i++) {
arr.push(random() * n);
arr1.push(arr[i]);
}
this.alterLine('MaxHeap Is Heapify Area');
const maxHeapIsHeapifyInfo = performanceTest1.testHeap(
maxHeapIsHeapify,
arr,
true
);
console.log(maxHeapIsHeapifyInfo);
this.show(maxHeapIsHeapifyInfo);
this.alterLine('MaxHeap Not Heapify Area');
const maxHeapNotHeapifyInfo = performanceTest1.testHeap(
maxHeapNotHeapify,
arr1,
false
);
console.log(maxHeapNotHeapifyInfo);
this.show(maxHeapNotHeapifyInfo);
// this.alterLine("MyMaxHeap Replace Area");
// const n = 20;
// const maxHeap = new MyMaxHeap();
// const random = Math.random;
// // 循环添加随机数的值
// for (let i = 0; i < n; i++)
// maxHeap.add(random() * n);
// console.log("MaxHeap maxHeap size:" + maxHeap.size());
// this.show("MaxHeap maxHeap size:" + maxHeap.size());
// // 使用数组取值
// let arr = [];
// for (let i = 0; i < n ; i++)
// arr[i] = maxHeap.replace(0);
// console.log("Array arr size:" + arr.length + "，MaxHeap maxHeap size:" + maxHeap.size());
// this.show("Array arr size:" + arr.length + "，MaxHeap maxHeap size:" + maxHeap.size());
// console.log(arr, maxHeap);
// // 检验一下是否符合要求
// for (let i = 1; i < n; i++)
// if (arr[i - 1] < arr[i]) throw new Error("error.");
// console.log("test maxHeap completed.");
// this.show("test maxHeap completed.");
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};堆的时间复杂度分析
堆中的时间复杂度都是O(logn)级别的：其实还是二叉树的高度这个级别的，对于堆来说它是一棵完全二叉树，所以它永远不会退化成一个链表，一棵完全二叉树它的高度和节点的数量之间的关系一定是logn这个级别的关系，这使得堆中相应的 add、extractMax 操作是非常的高效的。
将 n 个元素逐个插入到一个空堆中，算法复杂度是 O(nlogn)级别。如果使用 heapify 的过程，算法复杂度就为 O(n)级别的。同样把一个数组整理成堆的过程要比以逐个插入到空堆中要快一些。其实使用 heapify 与不使用 heapify 是有一个质的提升，这个提升是O(n)与O(nlogn)的区别。
上浮操作 Sift Up 与下沉操作 Sift Down，上浮是当前节点值与其父节点进行对比，如果当前节点大于其父节点就进行位置的交换。下沉是当前节点值与其左右两孩子节点中最大的值的节点进行对比，如果当前节点值比左右孩子节点最大值的那个节点值小，那么当前节点就和那个最大值孩子节点交换位置。
add O(logn)
extractMax O(logn)
replace O(logn)
heapify O(nlogn)
总结
实现的这个堆其实是二叉堆 Binary Heap。计算机世界中其实还有各种各样的堆，学会了二叉堆之后，最容易拓展的就是 d 叉堆 d-ary heap 了。也就是说，对于每一个节点来说，它可能有三个四个甚至更多个孩子，也排列成完全 d 叉树这种形式，用这样的方式也可以构建出一个堆来。
对于这种堆而言，其实它的层数是更加的低了，那么对它的添加操作删除操作，相应的时间复杂度都变成了 log 以 d 为底 n 这样的时间复杂度。从这个时间复杂度的角度来讲，好像比 log 以 2 为底 n 这样的时间复杂度要好，可是相应的代价会越高。比如每一个节点的 SiftDown 下沉操作时，需要考虑的节点数变多了，不仅仅是考虑两个节点了，而是要考虑 d 个节点，那么它们之间就存在了一个制衡的关系。
自己实现的堆有一个很大的缺点。只能看到堆首的元素，却不能看到堆中间的元素，实际上在很多应用中是需要看到堆中间的元素，甚至需要对堆中间的元素进行一定的修改。
在这种情况下相应的就要有一个索引堆这样的数据结构，这种堆除了保持你关注的那个元素之外，还对应了一个索引，可以通过这个索引非常方便的检索到元素存在堆中的哪个位置。甚至可以根据索引来修改这个元素，事实上索引堆还是应用非常广泛的一种数据结构，不过这种数据结构相对是比较高级的。
之后我也会更新索引堆进来，不过可能会比较慢噢，在慕课网《算法与数据结构》中第四章 8-9 节有索引堆的内容。无论是最小生成树算法还是最短路径算法，也就是对于 Prim 算法和 Dijkstra 算法都可以使用索引堆进行优化。
除了以上提到过的那些堆，在计算机的世界中还有各种奇奇怪怪的堆，二项堆、斐波那契堆，这些堆更是更高级的数据结构。
学习了堆这种数据结构的思想，可以去leetcode中去刷一刷堆相关的题目。 https://leetcode-cn.com/tag/heap/
