从二叉堆进阶到堆排序与优先队列,前端大佬都这样学...

一、二叉堆分类

大根堆

在是完全二叉树的前提下,其节点值大于其左右子节点值,称为大根堆。在大根堆中根节点是所有堆节点中的最大值。

小根堆

在是完全二叉树的前提下,其节点值小于其左右子节点值,称为小根堆。在小根堆中根节点是所有堆节点中的最小值。

二、二叉堆的存储

上述阐述了二叉堆其实就是一棵完全二叉树,然后数据满足某些特性,那么在编程中应该如何存储这些数据呢?这些数据间满足那些关系呢?

1.以数组结构存储二叉堆

在编程中我们会以数组存储二叉堆,以上述的最大堆为例,存储到数组中为如下结构:

2.二叉堆中父子节点间满足何种关系

既然数据将存储到数组中,那么就必须知道父子节点之间的关系,即:

(1)在知道父节点的索引的时候必须找到其对应的子节点;

(2)在知道子节点的索引的时候找到其对应的父节点;

如下的二叉堆,设置其根节点索引为0,然后依次递增:

已知某节点的索引为i,则其左右子节点索引为:

  • 左节点索引 = 2 * i + 1
  • 右节点索引 = 左节点索引 + 1

已知某节点的索引为i,则其父节点索引为:

  • 父节点 = parseInt((i - 1) / 2)

三、堆的基本操作

当遇到二叉堆的时候,我们应该学会如何构建一个大根堆(小根堆),这个时候就涉及到加堆和减堆的过程,下面让从加堆和减堆开始,从而使我们能够丝滑般的了解整个二叉堆的构建过程。(注:下面的例子以大根堆为例)

// 注:此处是封装的交换数组中元素的方法
// 数组中交换数据
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

1.加堆

加堆的过程实际上就是再往堆里面加入一个新的元素,然后维护该堆结构的过程,实际上就是在数组尾部加入一个元素,然后通过不断上浮,使其又调整为二叉堆结构的过程。


// 大根堆加堆过程中
function heapInsert(arr, index) {
// 比较当前位置和其父位置,若大于其父位置,则进行交换,并将索引移动到其父位置进行循环,否则跳过
// 结束条件是比其父位置小或者到达根节点处
while (index > 0 && arr[index] > arr[parseInt((index - 1) / 2)]) {
swap(arr, index, parseInt((index - 1) / 2));
index = parseInt((index - 1) / 2);
}

return arr;
}

有了加堆的过程,很容易我们就可以实现创建二叉堆,如下所示:

// 创建二叉堆
function createBigTopHeap(arr) {
for (let i = 0; i < arr.length; i++) {
arr = heapInsert(arr, i);
}

return arr;
}


const arr = [1, 5, 9, 10, 8, 12];

console.log(createBigTopHeap(arr)); // [ 12, 9, 10, 1, 8, 5 ]

2.减堆

减堆的过程就是将堆顶元素A和最后元素B交换,然后删除A元素并将B元素调整到合适的位置的过程,实际上就是将堆顶数据交换后,下沉数据的过程

// 减堆过程
// size指的是这个数组前多少个数构成一个堆
// 如果想把堆顶弹出,则把堆顶和最后一个数交换,把size减1,然后从0位置经历一次heapify,调整一下,剩余部分变成大顶堆
function heapify(arr, index, size) {
// 获取其左节点索引
let left = 2 * index + 1;
while (left < size) {
// 判断一下左右子节点哪个值最大,获取其最大值
let largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
// 判断左右子节点最大值与当前要比较的节点哪个大
largest = arr[index] > arr[largest] ? index : largest;

// 如果最大值索引和传进来的索引一样,则该值到达指定位置,直接结束循环
if (index === largest) {
break;
}

// 进行交换,改变索引及其左子节点
swap(arr, index, largest);
index = largest;
left = 2 * index + 1;
}

return arr;
}

const arr = [1, 5, 9, 10, 8, 12];

console.log(createBigTopHeap(arr));

// 交换堆顶数据与最后位置数据
swap(arr, 0, arr.length - 1);

// 通过下沉的方式获取新的堆结果
console.log(heapify(arr, 0, arr.length - 1));

四、叉堆的用途

因为二叉堆能够高效的找出最大值和最小值,所以可用于堆排序和构建优先队列。

1.堆排序

堆排序是常见的一种排序算法,整个堆排序过程如下所示:

  • 让数组变成大根堆。
  • 把最后一个位置和堆顶交换。
  • 则最大值在最后,则剩余部分做heapify,则重新调整为大根堆,则堆顶位置和该部分最后位置做交换。
  • 重复进行,直到减完,则这样最后就调整完毕,整个数组排完序(为一个升序)。
function heapSort(arr) {
if (arr === null || arr.length === 0) {
return [];
}

// 首先创建大根堆
for (let i = 0; i < arr.length; i++) {
arr = heapInsert(arr, i);
}

let size = arr.length; // 这个值用来指定多少个数组构成堆

// 由于当前已经是大根堆,所以直接交换
swap(arr, 0, --size);

while (size > 0) {
// 重新变成大顶堆
heapify(arr, 0, size);
// 进行交换
swap(arr, 0, --size);
}

return arr;
}

const arr = [1, 5, 9, 10, 8, 12];

console.log(heapSort(arr)); // [ 1, 5, 8, 9, 10, 12

2.优先队列

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

优先队列的插入

优先队列中元素的插入就是上述heapInsert过程,通过将元素添加到数组末尾,然后通过上浮的方式将内容插入到合适位置。

优先队列中元素的删除

优先队列中元素的删除就是将根节点的元素与最后元素交换,然后将交换后的根节点下沉,调整到合适位置,重新构成二叉堆。

网站栏目:从二叉堆进阶到堆排序与优先队列,前端大佬都这样学...
文章来源:http://www.shufengxianlan.com/qtweb/news29/333279.html

网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联