堆数据结构

提示

定义和类型：堆是一种满足特定堆属性的完全二叉树，可分为最大堆（父节点大于子节点）和最小堆（父节点小于子节点）。
基本操作：包括堆化（将二叉树转换为堆结构）、插入元素、删除元素以及提取最大或最小值。
堆的特点：堆化是创建最大或最小堆的关键步骤，涉及多次交换来保持堆属性；插入和删除操作后需重新堆化以维持堆结构。

堆数据结构是一种满足堆属性的完全二叉树，其中任何给定节点：

总是大于其子节点，并且根节点的键值是所有其他节点中最大的。这个属性也称为最大堆属性。
总是小于其子节点，并且根节点的键值是所有其他节点中最小的。这个属性也称为最小堆属性。

最大堆

最小堆

这种类型的数据结构也称为二叉堆。

堆操作

堆上执行的一些重要操作如下所述，以及它们的算法。

堆化（Heapify）

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

让输入数组为
从数组创建一个完全二叉树
从索引为 n/2 - 1 的第一个非叶节点开始。
将当前元素 i 设置为最大。
左子节点的索引为 2i + 1，右子节点的索引为 2i + 2。如果 leftChild 大于 currentElement（即在第 ith 索引处的元素），则将 leftChildIndex 设置为 largest。如果 rightChild 大于 largest 中的元素，则将 rightChildIndex 设置为 largest。
交换 largest 和 currentElement。
重复步骤 3-7，直到子树也堆化。

算法

Heapify(array, size, i)
  将 i 设置为 largest
  左子节点 = 2i + 1
  右子节点 = 2i + 2

  如果左子节点大于 array[largest]
    将左子节点索引设置为 largest
  如果右子节点大于 array[largest]
    将右子节点索引设置为 largest

  交换 array[i] 和 array[largest]

要创建最大堆：

MaxHeap(array, size)
  从第一个非叶节点的索引开始循环到零
    调用堆化函数

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

插入元素到堆

在最大堆中插入的算法

如果没有节点，
  创建一个新节点。
否则（节点已经存在）
  将新节点插入到树的末尾（从左到右的最后一个节点）。

堆化数组

将新元素插入到树的末尾。
堆化树。

堆中的插入

对于最小堆，上述算法被修改，以便parentNode 总是小于 newNode。

从堆中删除元素

在最大堆中删除的算法

如果要删除的节点是叶节点
  删除节点
否则将要删除的节点与最后一个叶节点交换
  删除要删除的节点

堆化数组

选择要删除的元素。
将其与最后一个元素交换。
删除最后一个元素。
堆化树。

堆中的删除

对于最小堆，上述算法被修改，以便childNodes 总是大于 currentNode。

Peek 获取最大/最小值

peek 操作用于返回最大堆中的最大元素或最小堆中的最小元素，而不删除节点。

对于最大堆和最小堆：

return rootNode

提取最大/最小值

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

Python、Java、C/C++ 示例

Python Java C C++

# Python 中的最大堆数据结构

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def insert(array, newNum):
    size = len(array)
    if size == 0:
        array.append(newNum)
    else:
        array.append(newNum);
        for i in range((size//2)-1, -1, -1):
            heapify(array, size, i)

def deleteNode(array, num):
    size = len(array)
    i = 0
    for i in range(0, size):
        if num == array[i]:
            break

    array[i], array[size-1] = array[size-1], array[i]

    array.remove(num)

    for i in range((len(array)//2)-1, -1, -1):
        heapify(array, len(array), i)

arr = []

insert(arr, 3)
insert(arr, 4)
insert(arr, 9)
insert(arr, 5)
insert(arr, 2)

print("最大堆数组: " + str(arr))

deleteNode(arr, 4)
print("删除一个元素后: " + str(arr))

// Java 中的最大堆数据结构

import java.util.ArrayList;

class Heap {
  void heapify(ArrayList<Integer> hT, int i) {
    int size = hT.size();
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && hT.get(l) > hT.get(largest))
      largest = l;
    if (r < size && hT.get(r) > hT.get(largest))
      largest = r;

    if (largest != i) {
      int temp = hT.get(largest);
      hT.set(largest, hT.get(i));
      hT.set(i, temp);

      heapify(hT, largest);
    }
  }

  void insert(ArrayList<Integer> hT, int newNum) {
    int size = hT.size();
    if (size == 0) {
      hT.add(newNum);
    } else {
      hT.add(newNum);
      for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(hT, i);
      }
    }
  }

  void deleteNode(ArrayList<Integer> hT, int num) {
    int size = hT.size();
    int i;
    for (i = 0; i < size; i++) {
      if (num == hT.get(i))
        break;
    }

    int temp = hT.get(i);
    hT.set(i, hT.get(size-1));
    hT.set(size-1, temp);

    hT.remove(size-1);
    for (int j = size / 2 - 1; j >= 0; j--)
    {
      heapify(hT, j);
    }
  }

  void printArray(ArrayList<Integer> array, int size) {
    for (Integer i : array) {
      System.out.print(i + " ");
    }
    System.out.println();
  }

  public static void main(String args[]) {

    ArrayList<Integer> array = new ArrayList<Integer>();
    int size = array.size();

    Heap h = new Heap();
    h.insert(array, 3);
    h.insert(array, 4);
    h.insert(array, 9);
    h.insert(array, 5);
    h.insert(array, 2);

    System.out.println("最大堆数组: ");
    h.printArray(array, size);

    h.deleteNode(array, 4);
    System.out.println("After deleting an element: ");
    h.printArray(array, size);
  }
}

// 在 C 中的最大堆数据结构

#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
  int temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(int array[], int size, int i)
{
  if (size == 1)
  {
    printf("堆中只有一个元素");
  }
  else
  {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && array[l] > array[largest])
      largest = l;
    if (r < size && array[r] > array[largest])
      largest = r;
    if (largest != i)
    {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
  }
}
void insert(int array[], int newNum)
{
  if (size == 0)
  {
    array[0] = newNum;
    size += 1;
  }
  else
  {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(array, size, i);
    }
  }
}
void deleteRoot(int array[], int num)
{
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == array[i])
      break;
  }

  swap(&array[i], &array[size - 1]);
  size -= 1;
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(array, size, i);
  }
}
void printArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
    printf("%d ", array[i]);
  printf("\n");
}
int main()
{
  int array[10];

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

  printf("最大堆数组: ");
  printArray(array, size);

  deleteRoot(array, 4);

  printf("删除元素后: ");

  printArray(array, size);
}

// 在 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 << "最大堆数组: ";
  printArray(heapTree);

  deleteNode(heapTree, 4);

  cout << "删除元素后: ";

  printArray(heapTree);
}

堆数据结构的应用

堆在实现优先队列时使用。
迪杰斯特拉算法
堆排序

堆数据结构

堆操作​

堆化（Heapify）​

插入元素到堆​

从堆中删除元素​

Peek 获取最大/最小值​

提取最大/最小值​

Python、Java、C/C++ 示例​

堆数据结构的应用​

堆操作