记录每一次成长

堆数据结构是一种满足堆属性的完全二叉树，其中任意给定的节点都（满足以下条件）

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

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

堆的操作

下面将介绍一些在堆上执行的重要操作及其算法。

堆化

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

设输入数组为

从该数组创建一棵完全二叉树

从第一个非叶子节点的索引开始，该非叶子节点的索引由n/2 - 1给出

将当前元素 i 设置为最大元素。
左子节点的索引由 2i + 1 给出，右子节点的索引由 2i + 2 给出。如果左子节点leftChild的值大于当前元素currentElement（即索引为 i 处的元素），则将左子节点的索引设为最大元素的索引。如果右子节点rightChild的值大于最大元素处的元素值，则将右子节点的索引设为最大元素的索引。
将最大元素与当前元素进行交换。

重复步骤 3 到 7，直到所有子树也都完成堆化。

算法

Heapify(array, size, i)
  set i as largest
  leftChild = 2i + 1
  rightChild = 2i + 2
  
  if leftChild > array[largest]
    set leftChildIndex as largest
  if rightChild > array[largest]
    set rightChildIndex as largest

  swap array[i] and array[largest]

要创建一个最大堆：

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

对于最小堆，对于所有节点而言，左子节点和右子节点的值都必须大于它们的父节点的值。

向堆中插入元素

最大堆插入操作的算法

If there is no node, 
  create a newNode.
else (a node is already present)
  insert the newNode at the end (last node from left to right.)
  
heapify the array

将新元素插入到树的末尾

对这棵树进行堆化处理

对于最小堆，上述算法需要进行修改，使得父节点的值始终小于新节点的值。

删除堆中的元素

最大堆中删除操作的算法

If nodeToBeDeleted is the leafNode
  remove the node
Else swap nodeToBeDeleted with the lastLeafNode
  remove noteToBeDeleted
   
heapify the array

选择要删除的元素。

将它与最后一个元素进行交换

移除最后一个元素

对这棵树进行堆化处理

查看（查找最大 / 最小值）

查看操作会从最大堆中返回最大元素，或者从最小堆中返回最小元素，并且不会删除该节点。对于最大堆和最小堆而言

return rootNode

提取最大 / 最小值

“提取最大值” 操作会在从最大堆中移除具有最大值的节点后返回该节点，而 “提取最小值” 操作则会在从最小堆中移除具有最小值的节点后返回该节点

Python、Java、C/C++ 示例

PythonJavaCC++

Python

# Max-Heap data structure in Python
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    
    if l < n and arr[l] > arr[largest]:
        largest = l
    
    if r < n and arr[r] > arr[largest]:
        largest = r
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def insert(array, newNum):
    array.append(newNum)
    current = len(array) - 1
    while current > 0:
        parent = (current - 1) // 2
        if array[current] > array[parent]:
            array[current], array[parent] = array[parent], array[current]
            current = parent
        else:
            break

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

    # Swap with the last element
    array[i], array[-1] = array[-1], array[i]
    array.pop()  # Remove the last element which is now the number to be deleted

    # Only run heapify if the deleted node was not the last node
    if i < len(array):
        heapify(array, len(array), i)

arr = []

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

print("Max-Heap array:", arr)

deleteNode(arr, 4)
print("After deleting an element:", arr)

Java


// Max-Heap data structure in 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("Max-Heap array: ");
    h.printArray(array, size);

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

// Max-Heap data structure in C
#include <stdio.h>

int size = 0;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int array[], int size, int i) {
    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) {
    array[size] = newNum;
    size += 1;

    int current = size - 1;
    while (current != 0) {
        int parent = (current - 1) / 2;
        if (array[current] > array[parent]) {
            swap(&array[current], &array[parent]);
            current = parent;
        } else {
            break;
        }
    }
}

void deleteRoot(int array[], int num) {
    int i;
    for (i = 0; i < size; i++) {
        if (array[i] == num) break;
    }

    swap(&array[i], &array[size - 1]);
    // Reduce the size of the heap since the last element is now removed
    size -= 1;

    // Heapify from the current index to adjust the rest of the heap
    if (i < size) {
        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("Max-Heap array: ");
    printArray(array, size);

    deleteRoot(array, 4);
    printf("After deleting an element: ");
    printArray(array, size);

    return 0;
}

C++

// Max-Heap data structure in C++
#include <iostream>
#include <vector>
using namespace std;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = 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) {
    hT.push_back(newNum);
    int current = hT.size() - 1;

    // Bubble up
    while (current > 0) {
        int parent = (current - 1) / 2;
        if (hT[current] > hT[parent]) {
            swap(&hT[current], &hT[parent]);
            current = parent;
        } else {
            break;
        }
    }
}

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();
    // Update size after popping
    size = hT.size();  

    // Heapify from the current index to adjust the rest of the heap
    if (i < size) {
        heapify(hT, i);
    }
}

void printArray(const vector<int> &hT) {
    for (int num : hT)
        cout << num << " ";
    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);

    return 0;
}

堆数据结构的应用

堆在实现优先队列时会被用到。
迪杰斯特拉算法（Dijkstra 算法）
堆排序

堆的操作 ​

堆化 ​

算法 ​

向堆中插入元素 ​

删除堆中的元素 ​

查看（查找最大 / 最小值） ​

提取最大 / 最小值 ​

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

堆数据结构的应用 ​