# 堆數據結構 > 原文： [https://www.programiz.com/dsa/heap-data-structure](https://www.programiz.com/dsa/heap-data-structure) #### 在本教程中，您將學習什么是堆數據結構。 此外，您還將找到在 C，C++ ，Java 和 Python 中進行堆操作的工作示例。 堆數據結構是滿足**堆屬性**的完全二叉樹，也稱為二叉堆。 完全二叉樹是一種特殊的二叉樹，其中 * 除最后一個級別外，每個級別都已填充 * 所有節點都盡可能地向左  堆屬性是其中節點的屬性 * （對于最大堆）每個節點的鍵始終大于其子節點，并且根節點的鍵在所有其他節點中最大；  * （對于最小堆）每個節點的鍵始終小于子節點，而根節點的鍵在所有其他節點中最小。  * * * ## 堆操作 下面將對在堆上執行的一些重要操作及其算法進行描述。 ### 建堆 建堆是從二叉樹創建堆數據結構的過程。 它用于創建最小堆或最大堆。 1. 令輸入數組為  2. 從數組創建完全二叉樹  3. 從索引為`n/2 - 1`的非葉節點的第一個索引開始。  4. 將當前元素`i`設置為`largest`。 5. 左子索引由`2i + 1`給出，右子索引由`2i + 2`給出。 如果`leftChild`大于`currentElement`（即位于`ith`索引處的元素），則將`leftChildIndex`設置為最大。 如果`rightChild`大于`largest`中的元素，請將`rightChildIndex`設置為`largest`。 6. 將`largest`與`currentElement`交換 7. 重復步驟 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 ``` 對于最小堆，對于所有節點，`leftChild`和`rightChild`都必須小于父節點。 * * * ### 將元素插入堆 最大堆中的插入算法 ``` 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 ``` 1. 在樹的末尾插入新元素。  2. 對樹建堆。  對于最小堆，對上述算法進行了修改，以使`parentNode`始終小于`newNode`。 * * * ### 從堆中刪除元素 最大堆中的刪除算法 ``` If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array ``` 1. 選擇要刪除的元素。  2. 將其與最后一個元素交換。  3. 刪除最后一個元素。  4. 對樹建堆。  對于最小堆，對上述算法進行了修改，以使`childNodes`均小于`currentNode`。 * * * ### 窺視（找到最大/最小） 窺視操作從最大堆中返回最大元素，或者從最小堆中返回最小元素，而不刪除節點。 對于最大堆和最小堆 ``` return rootNode ``` * * * ### 提取最大/最小 從最大堆中刪除后，`Extract-Max`返回具有最大值的節點，而從最小堆中刪除后，`Extract-Min`返回具有最小值的節點。 * * * ## Python，Java，C/C++ 示例 ```py # 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[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(size-1) 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 ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(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); } } ``` ```c // Max-Heap data structure in 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("Single element in the heap"); } 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("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); } ``` ```cpp // 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 算法 * 堆排序