二叉堆解析和详细实现原理解读

2021年4月3日18:44:49 发表评论 1,462 次浏览

本文概述

C++实现
python
C#

二叉堆是具有以下属性的二叉树。

1)这是一棵完整的树(除了最后一个级别, 所有级别都已完全填充, 并且最后一个级别的所有键都尽可能保留)。 Binary Heap的此属性使它们适合存储在数组中。

2)二叉堆是最小堆或最大堆。在最小二叉堆中, 在二叉堆中存在的所有密钥中, 根密钥必须最小。对于二叉树中的所有节点, 相同的属性必须递归地为true。 Max Binary Heap与MinHeap类似。

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

二叉堆如何表示？

二叉堆是完整的二叉树。二叉堆通常表示为数组。

下表为第i个节点的其他节点索引，即Arr[i]:

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

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

请参考二叉堆的数组表示有关详细信息。

堆的应用：1)

堆排序：堆排序使用二叉堆对O(nLogn)时间中的数组进行排序。

2)优先级队列：优先级队列可以使用Binary Heap有效地实现, 因为它支持O(logn)时间中的insert(), delete()和extractmax(), reducingKey()操作。 Binomoial堆和Fibonacci堆是Binary堆的变体。这些变化也有效地执行了合并。

3)图算法：优先级队列尤其用于图算法中, 例如迪克斯特拉的最短路径和Prim的最小生成树.

4)使用堆可以有效地解决许多问题。例如, 请参见以下内容。

c)合并K个排序的数组

最小堆操作：

1)getMini()：返回最小堆的根元素。该操作的时间复杂度为O(1)。

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

3)reductionKey()：减小键的值。此操作的时间复杂度为O(Logn)。如果节点的减键值大于节点的父键值, 则我们无需执行任何操作。否则, 我们需要遍历以修复违反的堆属性。

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

5)delete()：删除密钥也需要O(Logn)时间。我们通过调用reduceKey()用mininfinite替换要删除的键。在reduceKey()之后, 负无穷大值必须到达根, 因此我们调用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 << "\nOverflow: Could not insertKey\n" ;
         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库中的二叉堆实现

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

a)数组中的第K个最大元素

b)排序几乎排序的数组/