摘要:二叉堆數據結構是一種特殊的二叉樹,他能高效快速的找出最大值和最小值,常應用于優先隊列和著名的堆排序算法中。
二叉堆數據結構是一種特殊的二叉樹,他能高效、快速的找出最大值和最小值,常應用于優先隊列和著名的堆排序算法中。
二叉堆二叉堆有以下兩個特性:
是一顆完全二叉樹,表示數的每一層都有左側和右側子節點(除最后一層的葉節點),并且最后一層的葉節點盡可能是左側子節點
二叉堆不是最小堆就是最大堆,所有節點都大于等于(最大堆)或者小于等于(最小堆)每個他的子節點。
創建最小堆類</>復制代碼
class MinHeap {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
this.heap = [];
}
}
二叉堆的數組表示
</>復制代碼
static getLeftIndex(index) {
return (2 * index) + 1;
}
static getRightIndex(index) {
return (2 * index) + 2;
}
static getParentIndex(index) {
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];
}
交換函數實現
</>復制代碼
function swap(array, a, b) {
/* const temp = array[a];
array[a] = array[b];
array[b] = temp; */
[array[a], array[b]] = [array[b], array[a]];
}
向堆中插入新值
</>復制代碼
insert(value) {
if (value != null) {
const index = this.heap.length;
this.heap.push(value);
this.siftUp(index);
return true;
}
return false;
};
//上移操作
siftUp(index) {
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;
};
//下移操作
siftDown(index) {
let element = index;
const left = MinHeap.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);
}
}
創建最大堆類
</>復制代碼
class MaxHeap extends MinHeap {
constructor(compareFn = defaultCompare) {
super(compareFn);
this.compareFn = compareFn;
this.compareFn = reverseCompare(compareFn);
}
}
其他操作跟最小堆類一樣,這里就不多加贅述。
堆排序算法</>復制代碼
heapify(array) {
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;
};
//構建最大堆函數
function buildMaxHeap(array, compareFn) {
for (let i = Math.floor(array.length / 2);i >= 0; i -= 1){
heapify(array, i, array.length, compareFn);
return array;
}
}
//堆排序算法實現
function heapSort(array, compareFn = defaultCompare) {
let heapSize = array.length;
//用數組創建一個最大堆用作源數據
buildMaxHeap(array, compareFn);
while(heapSize > 1){
//創建最大堆后,最大的值會被存儲在堆的第一個位置,我們將它替換為堆的最后一個值,將堆的大小-1
swap(array, 0, --heapSize);
//將堆的根節點下移并重復步驟2直到堆的大小為1
heapify(array, 0, heapSize, compareFn);
}
return array;
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/106917.html
摘要:模型優先隊列是允許至少下列兩種操作的數據結構以及找出返回并刪除優先隊列中最小的元素。左式堆也是二叉樹,左式堆和二叉堆的唯一區別是左式堆不是理想平衡,而實際上趨向于非常不平衡。事實上,沿左式堆的右路徑是該堆中的最短路徑。 6.1 模型 優先隊列是允許至少下列兩種操作的數據結構:insert 以及 deleteMin(找出、返回并刪除優先隊列中最小的元素)。 insert 操作等價于 en...
摘要:二叉堆的有趣之處在于,其邏輯結構上像二叉樹,卻是用非嵌套的列表來實現。二叉堆結構性質為了更好地實現堆,我們采用二叉樹。圖完全二叉樹有意思的是我們用單個列表就能實現完全樹。下列所示的代碼是完全二叉堆的實現。 優先隊列的二叉堆實現 在前面的章節里我們學習了先進先出(FIFO)的數據結構:隊列(Queue)。隊列有一種變體叫做優先隊列(Priority Queue)。優先隊列的出隊(Dequ...
摘要:一個常見的例子就是優先隊列,還有排序算法之一的堆排序。另外我們還將學習堆排序,并將使用實現堆。堆排序在堆排序中,我們需要用給定的值構建一個一個堆。偽代碼如下從上面的偽代碼可以看到,堆排序的第一步就是構建一個堆。 堆是什么? 堆是基于樹抽象數據類型的一種特殊的數據結構,用于許多算法和數據結構中。一個常見的例子就是優先隊列,還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...
閱讀 775·2019-08-29 16:32
閱讀 844·2019-08-29 12:31
閱讀 3226·2019-08-26 18:26
閱讀 3168·2019-08-26 12:20
閱讀 1742·2019-08-26 12:00
閱讀 3014·2019-08-26 10:58
閱讀 2820·2019-08-23 17:08
閱讀 2315·2019-08-23 16:32