原文： https://www.programiz.com/dsa/heap-data-structure

在本教程中，您将学习什么是堆数据结构。 此外，您还将找到在 C，C++ ，Java 和 Python 中进行堆操作的工作示例。

堆数据结构是满足堆属性的完全二叉树，也称为二叉堆。

完全二叉树是一种特殊的二叉树，其中

  • 除最后一个级别外，每个级别都已填充
  • 所有节点都尽可能地向左

堆数据结构 - 图1

堆属性是其中节点的属性

  • （对于最大堆）每个节点的键始终大于其子节点，并且根节点的键在所有其他节点中最大；
    堆数据结构 - 图2
  • （对于最小堆）每个节点的键始终小于子节点，而根节点的键在所有其他节点中最小。

堆数据结构 - 图3

堆操作

下面将对在堆上执行的一些重要操作及其算法进行描述。

建堆

建堆是从二叉树创建堆数据结构的过程。 它用于创建最小堆或最大堆。

  1. 令输入数组为
    堆数据结构 - 图4
  2. 从数组创建完全二叉树
    堆数据结构 - 图5
  3. 从索引为n/2 - 1的非叶节点的第一个索引开始。
    堆数据结构 - 图6
  4. 将当前元素i设置为largest。
  5. 左子索引由2i + 1给出，右子索引由2i + 2给出。
    如果leftChild大于currentElement（即位于ith索引处的元素），则将leftChildIndex设置为最大。
    如果rightChild大于largest中的元素，请将rightChildIndex设置为largest。
  6. 将largest与currentElement交换
  7. 重复步骤 3-7，直到子树也被堆积。
    堆数据结构 - 图7

算法

  1. Heapify(array, size, i)
  2.   set i as largest
  3.   leftChild = 2i + 1
  4.   rightChild = 2i + 2
  6.   if leftChild > array[largest]
  7.     set leftChildIndex as largest
  8.   if rightChild > array[largest]
  9.     set rightChildIndex as largest
  11.   swap array[i] and array[largest]

要创建最大堆：

  1. MaxHeap(array, size)
  2.   loop from the first index of non-leaf node down to zero
  3.     call heapify

对于最小堆，对于所有节点，leftChild和rightChild都必须小于父节点。

将元素插入堆

最大堆中的插入算法

  1. If there is no node, 
  2.   create a newNode.
  3. else (a node is already present)
  4.   insert the newNode at the end (last node from left to right.)
  6. heapify the array
  1. 在树的末尾插入新元素。
    堆数据结构 - 图8
  2. 对树建堆。

堆数据结构 - 图9

对于最小堆，对上述算法进行了修改，以使parentNode始终小于newNode。

从堆中删除元素

最大堆中的删除算法

  1. If nodeToBeDeleted is the leafNode
  2.   remove the node
  3. Else swap nodeToBeDeleted with the lastLeafNode
  4.   remove noteToBeDeleted
  6. heapify the array
  1. 选择要删除的元素。
    堆数据结构 - 图10
  2. 将其与最后一个元素交换。
    堆数据结构 - 图11
  3. 删除最后一个元素。
    堆数据结构 - 图12
  4. 对树建堆。

堆数据结构 - 图13

对于最小堆，对上述算法进行了修改，以使childNodes均小于currentNode。

窥视（找到最大/最小）

窥视操作从最大堆中返回最大元素，或者从最小堆中返回最小元素，而不删除节点。

对于最大堆和最小堆

  1. return rootNode

提取最大/最小

从最大堆中删除后，Extract-Max返回具有最大值的节点，而从最小堆中删除后，Extract-Min返回具有最小值的节点。

Python，Java，C/C++ 示例

  1. # Max-Heap data structure in Python
  3. def heapify(arr, n, i):
  4.     largest = i
  5.     l = 2 * i + 1
  6.     r = 2 * i + 2 
  8.     if l < n and arr[i] < arr[l]:
  9.         largest = l
  11.     if r < n and arr[largest] < arr[r]:
  12.         largest = r
  14.     if largest != i:
  15.         arr[i],arr[largest] = arr[largest],arr[i]
  16.         heapify(arr, n, largest)
  18. def insert(array, newNum):
  19.     size = len(array)
  20.     if size == 0:
  21.         array.append(newNum)
  22.     else:
  23.         array.append(newNum);
  24.         for i in range((size//2)-1, -1, -1):
  25.             heapify(array, size, i)
  27. def deleteNode(array, num):
  28.     size = len(array)
  29.     i = 0
  30.     for i in range(0, size):
  31.         if num == array[i]:
  32.             break
  34.     array[i], array[size-1] = array[size-1], array[i]
  36.     array.remove(size-1)
  38.     for i in range((len(array)//2)-1, -1, -1):
  39.         heapify(array, len(array), i)
  41. arr = []
  43. insert(arr, 3)
  44. insert(arr, 4)
  45. insert(arr, 9)
  46. insert(arr, 5)
  47. insert(arr, 2)
  49. print ("Max-Heap array: " + str(arr))
  51. deleteNode(arr, 4)
  52. print("After deleting an element: " + str(arr))
  1.  // Max-Heap data structure in Java
  3. import java.util.ArrayList;
  5. class Heap {
  6.   void heapify(ArrayList<Integer> hT, int i) {
  7.     int size = hT.size();
  8.     int largest = i;
  9.     int l = 2 * i + 1;
  10.     int r = 2 * i + 2;
  11.     if (l < size && hT.get(l) > hT.get(largest))
  12.       largest = l;
  13.     if (r < size && hT.get(r) > hT.get(largest))
  14.       largest = r;
  16.     if (largest != i) {
  17.       int temp = hT.get(largest);
  18.       hT.set(largest, hT.get(i));
  19.       hT.set(i, temp);
  21.       heapify(hT, largest);
  22.     }
  23.   }
  25.   void insert(ArrayList<Integer> hT, int newNum) {
  26.     int size = hT.size();
  27.     if (size == 0) {
  28.       hT.add(newNum);
  29.     } else {
  30.       hT.add(newNum);
  31.       for (int i = size / 2 - 1; i >= 0; i--) {
  32.         heapify(hT, i);
  33.       }
  34.     }
  35.   }
  37.   void deleteNode(ArrayList<Integer> hT, int num)
  38.   {
  39.     int size = hT.size();
  40.     int i;
  41.     for (i = 0; i < size; i++)
  42.     {
  43.       if (num == hT.get(i))
  44.         break;
  45.     }
  47.     int temp = hT.get(i);
  48.     hT.set(i, hT.get(size-1));
  49.     hT.set(size-1, temp);
  51.     hT.remove(size-1);
  52.     for (int j = size / 2 - 1; j >= 0; j--)
  53.     {
  54.       heapify(hT, j);
  55.     }
  56.   }
  58.   void printArray(ArrayList<Integer> array, int size) {
  59.     for (Integer i : array) {
  60.       System.out.print(i + " ");
  61.     }
  62.     System.out.println();
  63.   }
  65.   public static void main(String args[]) {
  67.     ArrayList<Integer> array = new ArrayList<Integer>();
  68.     int size = array.size();
  70.     Heap h = new Heap();
  71.     h.insert(array, 3);
  72.     h.insert(array, 4);
  73.     h.insert(array, 9);
  74.     h.insert(array, 5);
  75.     h.insert(array, 2);
  77.     System.out.println("Max-Heap array: ");
  78.     h.printArray(array, size);
  80.     h.deleteNode(array, 4);
  81.     System.out.println("After deleting an element: ");
  82.     h.printArray(array, size);
  83.   }
  84. }
  1. // Max-Heap data structure in C
  3. #include <stdio.h>
  4. int size = 0;
  5. void swap(int *a, int *b)
  6. {
  7.   int temp = *b;
  8.   *b = *a;
  9.   *a = temp;
  10. }
  11. void heapify(int array[], int size, int i)
  12. {
  13.   if (size == 1)
  14.   {
  15.     printf("Single element in the heap");
  16.   }
  17.   else
  18.   {
  19.     int largest = i;
  20.     int l = 2 * i + 1;
  21.     int r = 2 * i + 2;
  22.     if (l < size && array[l] > array[largest])
  23.       largest = l;
  24.     if (r < size && array[r] > array[largest])
  25.       largest = r;
  26.     if (largest != i)
  27.     {
  28.       swap(&array[i], &array[largest]);
  29.       heapify(array, size, largest);
  30.     }
  31.   }
  32. }
  33. void insert(int array[], int newNum)
  34. {
  35.   if (size == 0)
  36.   {
  37.     array[0] = newNum;
  38.     size += 1;
  39.   }
  40.   else
  41.   {
  42.     array[size] = newNum;
  43.     size += 1;
  44.     for (int i = size / 2 - 1; i >= 0; i--)
  45.     {
  46.       heapify(array, size, i);
  47.     }
  48.   }
  49. }
  50. void deleteRoot(int array[], int num)
  51. {
  52.   int i;
  53.   for (i = 0; i < size; i++)
  54.   {
  55.     if (num == array[i])
  56.       break;
  57.   }
  59.   swap(&array[i], &array[size - 1]);
  60.   size -= 1;
  61.   for (int i = size / 2 - 1; i >= 0; i--)
  62.   {
  63.     heapify(array, size, i);
  64.   }
  65. }
  66. void printArray(int array[], int size)
  67. {
  68.   for (int i = 0; i < size; ++i)
  69.     printf("%d ", array[i]);
  70.   printf("\n");
  71. }
  72. int main()
  73. {
  74.   int array[10];
  76.   insert(array, 3);
  77.   insert(array, 4);
  78.   insert(array, 9);
  79.   insert(array, 5);
  80.   insert(array, 2);
  82.   printf("Max-Heap array: ");
  83.   printArray(array, size);
  85.   deleteRoot(array, 4);
  87.   printf("After deleting an element: ");
  89.   printArray(array, size);
  90. }
// Max-Heap data structure in C++

#include <iostream>
#include <vector>
using namespace std;

void swap(int *a, int *b)
{
  int temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(vector<int> &hT, int i)
{
  int size = hT.size();
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  if (l < size && hT[l] > hT[largest])
    largest = l;
  if (r < size && hT[r] > hT[largest])
    largest = r;

  if (largest != i)
  {
    swap(&hT[i], &hT[largest]);
    heapify(hT, largest);
  }
}
void insert(vector<int> &hT, int newNum)
{
  int size = hT.size();
  if (size == 0)
  {
    hT.push_back(newNum);
  }
  else
  {
    hT.push_back(newNum);
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(hT, i);
    }
  }
}
void deleteNode(vector<int> &hT, int num)
{
  int size = hT.size();
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == hT[i])
      break;
  }
  swap(&hT[i], &hT[size - 1]);

  hT.pop_back();
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(hT, i);
  }
}
void printArray(vector<int> &hT)
{
  for (int i = 0; i < hT.size(); ++i)
    cout << hT[i] << " ";
  cout << "\n";
}

int main()
{
  vector<int> heapTree;

  insert(heapTree, 3);
  insert(heapTree, 4);
  insert(heapTree, 9);
  insert(heapTree, 5);
  insert(heapTree, 2);

  cout << "Max-Heap array: ";
  printArray(heapTree);

  deleteNode(heapTree, 4);

  cout << "After deleting an element: ";

  printArray(heapTree);
}

堆数据结构应用

  • 在实现优先队列时使用堆。
  • Dijkstra 算法
  • 堆排序