跳过正文
  1. 数据结构与算法/

·403 字·2 分钟· loading
demo007x
作者
demo007x
目录

二叉堆
#

叉堆是一个 完整的二叉树,用于有效地存储数据,以根据其结构获取最大或最小元素。

二叉堆是最小堆或最大堆。在最小二叉堆中,根处的键必须是二叉堆中存在的所有键中最小的。对于二叉树中的所有节点,相同的属性必须递归地为真。最大二叉堆与最小堆类似。

最小堆的示例:

​ 10 10 ​ / \ / \
20 100 15 30
/ / \ /
30 40 50 100 40

二叉堆是如何表示的?
#

二叉堆是一棵完全二叉树。二叉堆通常表示为数组。

  • 根元素将位于 Arr[0]。
  • 下表显示了第 i个节点,即 Arr[i] 的其他节点的索引:
到达[(i-1)/2] 返回父节点
到达[(2*i)+1] 返回左子节点
到达[(2*i)+2] 返回右子节点

实现数组表示的遍历方法是 层序遍历。详细请参考 二叉堆的数组表示。

二叉堆树

堆上的操作:
#

以下是最小堆上的一些标准操作:

  • getMin():返回最小堆的根元素。该操作的时间复杂度为O(1)。如果是 maxheap ,则为getMax()
  • extractMin():从 MinHeap 中删除最小元素。此操作的时间复杂度为O(log N) ,因为此操作需要在删除根后维护堆属性(通过调用heapify() )。
  • DecreaseKey():减少键的值。此操作的时间复杂度为O(log N)。如果一个节点减少的键值大于该节点的父节点,那么我们不需要做任何事情。否则,我们需要向上遍历来修复违规的堆属性。
  • **insert():插入新键需要O(log N)**时间。我们在树的末尾添加一个新键。如果新值大于其父值,那么就不需要执行任何操作。否则,我们需要向上遍历来修复相关的值的顺序,保证堆固有属性。
  • **delete():删除一个键也需要O(log N)**时间。**我们通过调用DecreaseKey()将要删除的键替换为最小无限。在decreaseKey()之后,负无穷值必须到达根,因此我们调用extractMin()**来删除对应的值。

下面是基本堆操作的实现。
#

// A class for Min Heap
class MinHeap
{
	// Constructor: Builds a heap from a given array a[] of given size
	constructor()
	{
		this.arr = [];
	}

	left(i) {
		return 2*i + 1;
	}

	right(i) {
		return 2*i + 2;
	}

	parent(i){
		return Math.floor((i - 1)/2)
	}
	
	getMin()
	{
		return this.arr[0]
	}
	
	insert(k)
	{
		let arr = this.arr;
		arr.push(k);
	
		// Fix the min heap property if it is violated
		let i = arr.length - 1;
		while (i > 0 && arr[this.parent(i)] > arr[i])
		{
			let p = this.parent(i);
			[arr[i], arr[p]] = [arr[p], arr[i]];
			i = p;
		}
	}

	// Decreases value of key at index 'i' to new_val.
	// It is assumed that new_val is smaller than arr[i].
	decreaseKey(i, new_val)
	{
		let arr = this.arr;
		arr[i] = new_val;
		
		while (i !== 0 && arr[this.parent(i)] > arr[i])
		{
		let p = this.parent(i);
		[arr[i], arr[p]] = [arr[p], arr[i]];
		i = p;
		}
	}

	// Method to remove minimum element (or root) from min heap
	extractMin()
	{
		let arr = this.arr;
		if (arr.length == 1) {
			return arr.pop();
		}
		
		// Store the minimum value, and remove it from heap
		let res = arr[0];
		arr[0] = arr[arr.length-1];
		arr.pop();
		this.MinHeapify(0);
		return res;
	}


	// This function deletes key at index i. It first reduced value to minus
	// infinite, then calls extractMin()
	deleteKey(i)
	{
		this.decreaseKey(i, this.arr[0] - 1);
		this.extractMin();
	}

	// A recursive method to heapify a subtree with the root at given index
	// This method assumes that the subtrees are already heapified
	MinHeapify(i)
	{
		let arr = this.arr;
		let n = arr.length;
		if (n === 1) {
			return;
		}
		let l = this.left(i);
		let r = this.right(i);
		let smallest = i;
		if (l < n && arr[l] < arr[i])
			smallest = l;
		if (r < n && arr[r] < arr[smallest])
			smallest = r;
		if (smallest !== i)
		{
			[arr[i], arr[smallest]] = [arr[smallest], arr[i]]
			this.MinHeapify(smallest);
		}
	}
}

let h = new MinHeap();
	h.insert(3);
	h.insert(2);
	h.deleteKey(1);
	h.insert(15);
	h.insert(5);
	h.insert(4);
	h.insert(45);
	
	console.log(h.extractMin() + " ");
	console.log(h.getMin() + " ");
	
	h.decreaseKey(2, 1);
	console.log(h.extractMin());