- A+
所属分类：Web前端
简介
二叉堆是一种特殊的二叉树,但是不是一个二叉搜索树,二叉堆 是计算机科学中非常著名的数据结构,又称堆,由于其高效,快速地查找出最大值和最小值,常用于优先队列
结构
- 他是一棵完全二叉树,表示树的每一层都有左侧和右侧子节点(除了最后一层的叶子节点),
并且最后一层的叶节点尽可能在都在左侧,这个叫做结构特征 - 二叉堆不是最小堆就是最大堆.最小堆运行你快速导出最小值,最大堆允许你快速导出树的最大值.所有的节点都大于等于(最大堆),或小于等于(最小堆)每个它的子节点.这叫作堆特性.
尽管二叉堆是二叉树,但并不一定是二叉搜索树(BST).在二叉堆中,每个子节点都要大于等于父节点(最小堆)或小于等于父节点(最大堆).然而二叉搜索树中,左侧子节点总是比父节点小,右侧子节点也总是更大
创建我们的最小堆
选择存储数据的数据类型
这里可以选择和上一章树一样的数据类型(双指针,一个左指针,一个右指针),但是也可以使用数组
左节点: 当前节点下标 * 2 + 1
右节点:当前节点下标 * 2 + 2
父节点: (index - 1) / 2 (当位置可用时,这是一个边界,注意 )
基础方法
insert(value) : 这个方法向堆中插入一个新的值.如果插入成功,它返回true,否则返回false
extract(): 这个方法移除最小值(最小堆的时候)或最大值(最大堆的时候),并返回这个值
findMinimum():这个方法返回最小值(最小堆的时候)或最大值(最大堆的时候),但不会删除该值
基础方法
enum Compare { LESS_THAN = -1, BIGGER_THAN = 1, EQUALS = 0 } function defaultCompareFn<T>(parent: T, child: T) { if (parent === child) { return Compare.EQUALS } return parent > child ? Compare.BIGGER_THAN : Compare.LESS_THAN; } // 数组交换 function swap<T>(array: Array<T>, index: number, otherIndex: number) { [array[index], array[otherIndex]] = [array[otherIndex], array[index]]; } 这里添加一个枚举类型,表示
小于,大于,等于添加一个默认比较方法
添加一个数组交换的方法,因为经常要进行数组交换
基础结构
export class MinHeap<T> { private heap: Array<T>; compareFn: Function; constructor(compareFn: Function = defaultCompareFn) { //使用数组一定程度上不用去维护左右的指针 this.heap = []; //这个是一个比较大小的方法,与前面类似 this.compareFn = compareFn; } //获取左边子元素位置 getLeftIndex(index: number) { return index * 2 + 1; } //获取右边子元素位置 getRightIndex(index: number) { return index * 2 + 2; } //获取父节点元素位置 getParentIndex(index: number) { if (index === 0) { return undefined; } return Math.floor((index - 1) / 2); } isEmpty() { return this.heap.length <= 0; } size() { return this.heap.length; } clear() { this.heap = []; } } 这里是用的数组做存储,至于左右指针就以上面说的那样算
所以提供一个获取左右指针以及父指针的方法 + 以前经常用的方法
方法实现
insert方法
// 插入值 insert(value: T) { if (value != null) { //先插入到堆里去吧,这个是插入到最后,所以还要看这个数是否在这个位置 this.heap.push(value); //上移操作 this.siftUp(this.heap.length - 1); return true; } return false; } 这里是把值先push到数组中,添加到最尾部了,但是这个并不是说他就是在这个位置,所以需要进行数据
上移操作
siftUp操作(递归版)
siftUp(index: number) { //向上移动,所以与其父节点比较 let pIndex = this.getParentIndex(index); //父级节点大于当前节点,那么就要交换位置 if (index > 0 && this.compareFn(this.heap[pIndex], this.heap[index]) === Compare.BIGGER_THAN) { //将当前元素与父元素交换 swap(this.heap, pIndex, index); //交换完成后我们要进行下一步比较,我们插入的元素在pIndex位置,但是我们不知道他是否到了该在的位置,所以继续 this.siftUp(pIndex); } } 其实所谓的上移就是最简单的比较,我们现在弄最小堆,所以只要我们的
新插入的值 < 父节点值,那就说明我们需要上移,那么就交换位置,注意:这里上移一个位置后,我们的目标就改到了父节点上,所以我们递归的index变成了pIndex
siftUp操作(迭代版)
let parent = this.getParentIndex(index); while ( index > 0 && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN ) { swap(this.heap, parent, index); index = parent; parent = this.getParentIndex(index); } 注意事项同上
extract方法
移除最小值,基本思路就是
- 交换最后一个和第一个的位置
- 然后移除最后一个,并保存作为返回值
- 然后让第一个值向下找合适的位置(这里其实类似于上面的
siftUp,区别不过是以前是一个数比较,现在子节点有两个,但是要找到最小的那个,一定要记得是最小的那个哦!!!)- 为什么找最小的???[考虑第一次交换的情况,当前元素需要下移,并且在第一个节点上,需要找一个最小的放上面,作为根节点]
- 然后交换位置,然后继续下移,直到最后
extract() { //如果空,就不用移除了 if (this.isEmpty()) { return undefined; } //如果有一个元素,就可以直接移除返回 if (this.size() === 1) { return this.heap.shift(); } //最后一个和第一个交换 swap(this.heap, 0 , this.size() - 1) //弹出最后一个,并保留作为返回值 let result = this.heap.pop(); //开始向下移动 this.siftDown(0); return result; } siftDown操作
siftDown(index: number) { //获取左右的下标 let leftIndex = this.getLeftIndex(index); let rightIndex = this.getRightIndex(index); // 定义index值 element let element = index; // 在有效范围内和左边元素比较,如果大就向下移动 if(index < this.size() && this.compareFn(this.heap[element], this.heap[leftIndex]) === Compare.BIGGER_THAN){ element = leftIndex; } //*** 在有效范围内和右元素比较,如果大就向下移动 这里使用的是element,注意,因为element代表了最小的数 if(index < this.size() && this.compareFn(this.heap[element], this.heap[rightIndex]) === Compare.BIGGER_THAN){ element = rightIndex; } //确定位置结束 if(element !== index){ // 交换元素,下移当前元素 swap(this.heap, index , element); // 然后递归,继续移动当前元素,但是这个时候就不再是index,而是element this.siftDown(element); } } 这里一定要注意的是
***标注点处的使用element,因为index可能在左节点的时候被替换了,这里需要的是最小值
findMinimum方法
这个就不用多说了吧,就是取数组的第一个就好
//找最小的事 findMinimum() { return this.isEmpty() ? undefined : this.heap[0]; } 总结
到此
堆的所有方法就实现了,整体来说堆的边界不是很复杂,所以还是比较简单的一种
其他
你说还没结束,哦,好像是的,忘记了两件事,一个最喜欢的贴代码,一个就是
堆排序
function heapify(array: any[], index: number, heapSize: number, compareFn: Function) { let largest = index; const left = (2 * index) + 1; const right = (2 * index) + 2; if (left < heapSize && compareFn(array[left], array[index]) > 0) { largest = left; } if (right < heapSize && compareFn(array[right], array[largest]) > 0) { largest = right; } if (largest !== index) { swap(array, index, largest); heapify(array, largest, heapSize, compareFn); } } function buildMaxHeap(array: any[], compareFn: Function) { for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) { heapify(array, i, array.length, compareFn); } return array; } export function heapSort(array: any[], compareFn = defaultCompareFn) { let heapSize = array.length; buildMaxHeap(array, compareFn); while (heapSize > 1) { swap(array, 0, --heapSize); heapify(array, 0, heapSize, compareFn); } return array; } 方法就不多BB了,加油
所有代码
/* * 二叉堆是二叉数,但是不一定是二叉搜索树 * * insert(value) * extract():移除最大堆的最大值或者最小堆的最小值 * findMinimum():这个方法返回最小值(最小堆)或最大值(最大堆)且不会移除这个值 * * 二叉堆以数组存数据 下标找节点 * 初始节点: 0 * 1 2 * 3 4 5 6 * 7 8 9 10 11 12 13 14 * 0 * 第二排(下标1): 0 * 2 + 1 0 * 2 + 2 * 第三排(下标2): 1 * 2 + 1 1 * 2 + 2 2 * 2 + 1 2 * 2 + 2 * *总结: *左元素的位置: 当前下标 * 2 + 1 *右元素的位置: 当前下标 * 2 + 2 */ enum Compare { LESS_THAN = -1, BIGGER_THAN = 1, EQUALS = 0 } function defaultCompareFn<T>(parent: T, child: T) { if (parent === child) { return Compare.EQUALS } return parent > child ? Compare.BIGGER_THAN : Compare.LESS_THAN; } // 数组交换 function swap<T>(array: Array<T>, index: number, otherIndex: number) { [array[index], array[otherIndex]] = [array[otherIndex], array[index]]; } export class MinHeap<T> { private heap: Array<T>; compareFn: Function; constructor(compareFn: Function = defaultCompareFn) { this.heap = []; this.compareFn = compareFn; } //获取左边子元素位置 getLeftIndex(index: number) { return index * 2 + 1; } //获取右边子元素位置 getRightIndex(index: number) { return index * 2 + 2; } //获取父节点元素位置 getParentIndex(index: number) { if (index === 0) { return undefined; } return Math.floor((index - 1) / 2); } isEmpty() { return this.heap.length <= 0; } size() { return this.heap.length; } clear() { this.heap = []; } // 插入值 insert(value: T) { if (value != null) { //先插入到堆里去吧,这个是插入到最后,所以还要看这个数是否在这个位置 this.heap.push(value); this.siftUp(this.heap.length - 1); return true; } return false; } //以数组的形式返回数据 getAsArray() { return this.heap } // 向上移动数据 siftUp(index: number) { /* //向上移动,所以与其父节点比较 let pIndex = this.getParentIndex(index); //父级节点大于当前节点,那么就要交换位置 if (index > 0 && this.compareFn(this.heap[pIndex], this.heap[index]) === Compare.BIGGER_THAN) { //将当前元素与父元素交换 swap(this.heap, pIndex, index); //交换完成后我们要进行下一步比较,我们插入的元素在pIndex位置,但是我们不知道他是否到了该在的位置,所以继续 this.siftUp(pIndex); } */ let parent = this.getParentIndex(index); while ( index > 0 && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN ) { swap(this.heap, parent, index); index = parent; parent = this.getParentIndex(index); } } //找最小的事 findMinimum() { return this.isEmpty() ? undefined : this.heap[0]; } //移除堆中的最小值 extract() { //如果空,就不用移除了 if (this.isEmpty()) { return undefined; } //如果有一个元素,就可以直接移除返回 if (this.size() === 1) { return this.heap.shift(); } //最后一个和第一个交换 swap(this.heap, 0 , this.size() - 1) //弹出最后一个,并保留作为返回值 let result = this.heap.pop(); //开始堆化 this.siftDown(0); return result; } /** * 移动数据 * 使第一个元素找到其正确的位置 * 注意,此时的第一个元素是最大值(最小堆),所以这个时候只要向下找合适位置就可以了 * * 这个方法其实和向上找(siftUp)是基本一样的,但是区别就在是有左右两个节点,所以我们基于前面说的原则,找到最小的那个即可 */ siftDown(index: number) { //获取左右的下标 let leftIndex = this.getLeftIndex(index); let rightIndex = this.getRightIndex(index); // 定义index值 element let element = index; // 在有效范围内和左边元素比较,如果大就向下移动 if(index < this.size() && this.compareFn(this.heap[element], this.heap[leftIndex]) === Compare.BIGGER_THAN){ element = leftIndex; } // 在有效范围内和右元素比较,如果大就向下移动 这里使用的是element,注意,因为element代表了最小的数 if(index < this.size() && this.compareFn(this.heap[element], this.heap[rightIndex]) === Compare.BIGGER_THAN){ element = rightIndex; } //确定位置结束 if(element !== index){ // 交换元素,下移当前元素 swap(this.heap, index , element); // 然后递归,继续移动当前元素,但是这个时候就不再是index,而是element this.siftDown(element); } } heapify(array: T[]) { if (array) { this.heap = array; } const maxIndex = Math.floor(this.size() / 2) - 1; for (let i = 0; i <= maxIndex; i++) { this.siftDown(i); } return this.heap; } } function defaultMaxCompareFn<T>(parent: T, child: T) { if (parent === child) { return Compare.EQUALS } return parent > child ? Compare.LESS_THAN : Compare.BIGGER_THAN } export class MaxHeap<T> extends MinHeap<T> { constructor(compareFn = defaultMaxCompareFn) { super(compareFn); } } function heapify(array: any[], index: number, heapSize: number, compareFn: Function) { let largest = index; const left = (2 * index) + 1; const right = (2 * index) + 2; if (left < heapSize && compareFn(array[left], array[index]) > 0) { largest = left; } if (right < heapSize && compareFn(array[right], array[largest]) > 0) { largest = right; } if (largest !== index) { swap(array, index, largest); heapify(array, largest, heapSize, compareFn); } } function buildMaxHeap(array: any[], compareFn: Function) { for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) { heapify(array, i, array.length, compareFn); } return array; } export function heapSort(array: any[], compareFn = defaultCompareFn) { let heapSize = array.length; buildMaxHeap(array, compareFn); while (heapSize > 1) { swap(array, 0, --heapSize); heapify(array, 0, heapSize, compareFn); } return array; } 书本代码
enum Compare { LESS_THAN = -1, BIGGER_THAN = 1, EQUALS = 0 } function defaultCompare<T>(a: T, b: T): number { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; } type ICompareFunction<T> = (a: T, b: T) => number; function reverseCompare<T>(compareFn: ICompareFunction<T>): ICompareFunction<T> { return (a, b) => compareFn(b, a); } function swap(array: any[], a: number, b: number) { /* const temp = array[a]; array[a] = array[b]; array[b] = temp; */ [array[a], array[b]] = [array[b], array[a]]; } export class MinHeap<T> { protected heap: T[] = []; constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {} private getLeftIndex(index: number) { return 2 * index + 1; } private getRightIndex(index: number) { return 2 * index + 2; } private getParentIndex(index: number) { if (index === 0) { return undefined; } return Math.floor((index - 1) / 2); } size() { return this.heap.length; } isEmpty() { return this.size() <= 0; } clear() { this.heap = []; } findMinimum() { return this.isEmpty() ? undefined : this.heap[0]; } insert(value: T) { if (value != null) { const index = this.heap.length; this.heap.push(value); this.siftUp(index); return true; } return false; } private siftDown(index: number) { let element = index; const left = this.getLeftIndex(index); const right = this.getRightIndex(index); const size = this.size(); if (left < size && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN) { element = left; } if ( right < size && this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN ) { element = right; } if (index !== element) { swap(this.heap, index, element); this.siftDown(element); } } private siftUp(index: number): void { let parent = this.getParentIndex(index); while ( index > 0 && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN ) { swap(this.heap, parent, index); index = parent; parent = this.getParentIndex(index); } } extract() { if (this.isEmpty()) { return undefined; } if (this.size() === 1) { return this.heap.shift(); } const removedValue = this.heap[0]; this.heap[0] = this.heap.pop(); this.siftDown(0); return removedValue; } heapify(array: T[]) { if (array) { this.heap = array; } const maxIndex = Math.floor(this.size() / 2) - 1; for (let i = 0; i <= maxIndex; i++) { this.siftDown(i); } return this.heap; } getAsArray() { return this.heap; } } export class MaxHeap<T> extends MinHeap<T> { constructor(protected compareFn: ICompareFunction<T> = defaultCompare) { super(compareFn); this.compareFn = reverseCompare(compareFn); } } 表示这一周本来是说两个章节的,可是工作还有生活原因(这都是假的,主要是自己蠢,后面的图,迷迷糊糊的,唉!!!)
然后发现自己胖了,胖得不行了,所以下周开始减肥,并且满满的日程,但是学习不能断呀!!!还是会尽量基础时间学习,毕竟现在太弱鸡了,唉着急!!!!
下周排序,有兴趣的可以留意我一下哦!!!
