二进制堆

二进制堆是具有以下属性的二叉树。 1） 这是一个完整的树（除了最后一个级别，所有级别都被完全填充，最后一个级别尽可能地保留所有关键点）。二进制堆的这个特性使它们适合存储在数组中。

2） 二进制堆是最小堆或最大堆。在最小二进制堆中，根上的密钥必须是二进制堆中所有密钥中的最小密钥。对于二叉树中的所有节点，相同的属性必须递归为真。最大二进制堆类似于最小堆。

最小堆的示例：

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

二进制堆是如何表示的？ 二进制堆是一个完整的二叉树。二进制堆通常表示为数组。

• 根元素将位于Arr[0]。
• 下表显示了i的其他节点的索引 ^th 节点，即Arr[i]：
  

  Arr[（i-1）/2]	返回父节点
  Arr[（2*i）+1]	返回左子节点
  Arr[（2*i）+2]	返回正确的子节点

  用于实现数组表示的遍历方法是 水平顺序

  请参考 二进制堆的数组表示 详细信息。

  堆的应用： 1) 堆排序 ：Heap Sort使用二进制堆在O（nLogn）时间内对数组进行排序。

  2) 优先级队列：使用二进制堆可以有效地实现优先级队列，因为它支持在O（logn）时间内执行insert（）、delete（）和extractmax（）、decreaseKey（）操作。二进制堆和斐波那契堆是二进制堆的变体。这些变体也能有效地执行联合。

  3) 图算法：优先级队列特别用于图算法，如 Dijkstra的最短路径 和 普里姆最小生成树 .

  4) 使用堆可以有效地解决许多问题。例如，见下文。 （a） 数组中第K个最大元素 . b） 对几乎排序的数组进行排序/ c） 合并K排序数组 .

  最小堆上的操作： 1) getMini（）：它返回Min Heap的根元素。该操作的时间复杂度为O（1）。

  2) extractMin（）：从MinHeap中删除最小元素。此操作的时间复杂度为O（Logn），因为此操作需要在删除根后（通过调用heapify（））维护heap属性。

  3) decreaseKey（）：减少键的值。该操作的时间复杂度为O（Logn）。如果一个节点的reduces键值大于该节点的父节点，那么我们不需要做任何事情。否则，我们需要遍历up来修复违反的heap属性。

  4) insert（）：插入新密钥需要O（Logn）时间。我们在树的末尾添加一个新键。如果新密钥大于其父密钥，则无需执行任何操作。否则，我们需要遍历up来修复违反的heap属性。

  5) delete（）：删除密钥也需要O（Logn）时间。我们通过调用decreaseKey（）将要删除的密钥替换为minum infinite。在decreaseKey（）之后，负无穷大的值必须到达根，所以我们调用extractMin（）来移除该键。

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

  C++

  // A C++ program to demonstrate common Binary Heap Operations #include<iostream> #include<climits> using namespace std; // Prototype of a utility function to swap two integers void swap( int *x, int *y); // A class for Min Heap class MinHeap { int *harr; // pointer to array of elements in heap int capacity; // maximum possible size of min heap int heap_size; // Current number of elements in min heap public : // Constructor MinHeap( int capacity); // to heapify a subtree with the root at given index void MinHeapify( int ); int parent( int i) { return (i-1)/2; } // to get index of left child of node at index i int left( int i) { return (2*i + 1); } // to get index of right child of node at index i int right( int i) { return (2*i + 2); } // to extract the root which is the minimum element int extractMin(); // Decreases key value of key at index i to new_val void decreaseKey( int i, int new_val); // Returns the minimum key (key at root) from min heap int getMin() { return harr[0]; } // Deletes a key stored at index i void deleteKey( int i); // Inserts a new key 'k' void insertKey( int k); }; // Constructor: Builds a heap from a given array a[] of given size MinHeap::MinHeap( int cap) { heap_size = 0; capacity = cap; harr = new int [cap]; } // Inserts a new key 'k' void MinHeap::insertKey( int k) { if (heap_size == capacity) { cout << "Overflow: Could not insertKey" ; return ; } // First insert the new key at the end heap_size++; int i = heap_size - 1; harr[i] = k; // Fix the min heap property if it is violated while (i != 0 && harr[parent(i)] > harr[i]) { swap(&harr[i], &harr[parent(i)]); i = parent(i); } } // Decreases value of key at index 'i' to new_val.  It is assumed that // new_val is smaller than harr[i]. void MinHeap::decreaseKey( int i, int new_val) { harr[i] = new_val; while (i != 0 && harr[parent(i)] > harr[i]) { swap(&harr[i], &harr[parent(i)]); i = parent(i); } } // Method to remove minimum element (or root) from min heap int MinHeap::extractMin() { if (heap_size <= 0) return INT_MAX; if (heap_size == 1) { heap_size--; return harr[0]; } // Store the minimum value, and remove it from heap int root = harr[0]; harr[0] = harr[heap_size-1]; heap_size--; MinHeapify(0); return root; } // This function deletes key at index i. It first reduced value to minus // infinite, then calls extractMin() void MinHeap::deleteKey( int i) { decreaseKey(i, INT_MIN); extractMin(); } // A recursive method to heapify a subtree with the root at given index // This method assumes that the subtrees are already heapified void MinHeap::MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l] < harr[i]) smallest = l; if (r < heap_size && harr[r] < harr[smallest]) smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap( int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // Driver program to test above functions int main() { MinHeap h(11); h.insertKey(3); h.insertKey(2); h.deleteKey(1); h.insertKey(15); h.insertKey(5); h.insertKey(4); h.insertKey(45); cout << h.extractMin() << " " ; cout << h.getMin() << " " ; h.decreaseKey(2, 1); cout << h.getMin(); return 0; }

  python

  # A Python program to demonstrate common binary heap operations # Import the heap functions from python library from heapq import heappush, heappop, heapify # heappop - pop and return the smallest element from heap # heappush - push the value item onto the heap, maintaining #             heap invarient # heapify - transform list into heap, in place, in linear time # A class for Min Heap class MinHeap: # Constructor to initialize a heap def __init__( self ): self .heap = [] def parent( self , i): return (i - 1 ) / 2 # Inserts a new key 'k' def insertKey( self , k): heappush( self .heap, k) # Decrease value of key at index 'i' to new_val # It is assumed that new_val is smaller than heap[i] def decreaseKey( self , i, new_val): self .heap[i] = new_val while (i ! = 0 and self .heap[ self .parent(i)] > self .heap[i]): # Swap heap[i] with heap[parent(i)] self .heap[i] , self .heap[ self .parent(i)] = ( self .heap[ self .parent(i)], self .heap[i]) # Method to remove minium element from min heap def extractMin( self ): return heappop( self .heap) # This functon deletes key at index i. It first reduces # value to minus infinite and then calls extractMin() def deleteKey( self , i): self .decreaseKey(i, float ( "-inf" )) self .extractMin() # Get the minimum element from the heap def getMin( self ): return self .heap[ 0 ] # Driver pgoratm to test above function heapObj = MinHeap() heapObj.insertKey( 3 ) heapObj.insertKey( 2 ) heapObj.deleteKey( 1 ) heapObj.insertKey( 15 ) heapObj.insertKey( 5 ) heapObj.insertKey( 4 ) heapObj.insertKey( 45 ) print heapObj.extractMin(), print heapObj.getMin(), heapObj.decreaseKey( 2 , 1 ) print heapObj.getMin() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

  C#

  // C# program to demonstrate common // Binary Heap Operations - Min Heap using System; // A class for Min Heap class MinHeap{ // To store array of elements in heap public int [] heapArray{ get ; set ; } // max size of the heap public int capacity{ get ; set ; } // Current number of elements in the heap public int current_heap_size{ get ; set ; } // Constructor public MinHeap( int n) { capacity = n; heapArray = new int [capacity]; current_heap_size = 0; } // Swapping using reference public static void Swap<T>( ref T lhs, ref T rhs) { T temp = lhs; lhs = rhs; rhs = temp; } // Get the Parent index for the given index public int Parent( int key) { return (key - 1) / 2; } // Get the Left Child index for the given index public int Left( int key) { return 2 * key + 1; } // Get the Right Child index for the given index public int Right( int key) { return 2 * key + 2; } // Inserts a new key public bool insertKey( int key) { if (current_heap_size == capacity) { // heap is full return false ; } // First insert the new key at the end int i = current_heap_size; heapArray[i] = key; current_heap_size++; // Fix the min heap property if it is violated while (i != 0 && heapArray[i] < heapArray[Parent(i)]) { Swap( ref heapArray[i], ref heapArray[Parent(i)]); i = Parent(i); } return true ; } // Decreases value of given key to new_val. // It is assumed that new_val is smaller // than heapArray[key]. public void decreaseKey( int key, int new_val) { heapArray[key] = new_val; while (key != 0 && heapArray[key] < heapArray[Parent(key)]) { Swap( ref heapArray[key], ref heapArray[Parent(key)]); key = Parent(key); } } // Returns the minimum key (key at // root) from min heap public int getMin() { return heapArray[0]; } // Method to remove minimum element // (or root) from min heap public int extractMin() { if (current_heap_size <= 0) { return int .MaxValue; } if (current_heap_size == 1) { current_heap_size--; return heapArray[0]; } // Store the minimum value, // and remove it from heap int root = heapArray[0]; heapArray[0] = heapArray[current_heap_size - 1]; current_heap_size--; MinHeapify(0); return root; } // This function deletes key at the // given index. It first reduced value // to minus infinite, then calls extractMin() public void deleteKey( int key) { decreaseKey(key, int .MinValue); extractMin(); } // A recursive method to heapify a subtree // with the root at given index // This method assumes that the subtrees // are already heapified public void MinHeapify( int key) { int l = Left(key); int r = Right(key); int smallest = key; if (l < current_heap_size && heapArray[l] < heapArray[smallest]) { smallest = l; } if (r < current_heap_size && heapArray[r] < heapArray[smallest]) { smallest = r; } if (smallest != key) { Swap( ref heapArray[key], ref heapArray[smallest]); MinHeapify(smallest); } } // Increases value of given key to new_val. // It is assumed that new_val is greater // than heapArray[key]. // Heapify from the given key public void increaseKey( int key, int new_val) { heapArray[key] = new_val; MinHeapify(key); } // Changes value on a key public void changeValueOnAKey( int key, int new_val) { if (heapArray[key] == new_val) { return ; } if (heapArray[key] < new_val) { increaseKey(key, new_val); } else { decreaseKey(key, new_val); } } } static class MinHeapTest{ // Driver code public static void Main( string [] args) { MinHeap h = new MinHeap(11); h.insertKey(3); h.insertKey(2); h.deleteKey(1); h.insertKey(15); h.insertKey(5); h.insertKey(4); h.insertKey(45); Console.Write(h.extractMin() + " " ); Console.Write(h.getMin() + " " ); h.decreaseKey(2, 1); Console.Write(h.getMin()); } } // This code is contributed by // Dinesh Clinton Albert(dineshclinton)

  输出：

  2 4 1

  堆上的编码实践 堆上的所有文章 堆上测验 PriorityQueue:Java库中的二进制堆实现

  如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。