上查看所有课程
堆数据结构是一棵完全二叉树，它满足堆属性，即任何给定节点都
- 始终大于其子节点，并且根节点的键是所有其他节点中最大的。此属性也称为最大堆属性。
- 始终小于子节点，并且根节点的键是所有其他节点中最小的。此属性也称为最小堆属性。
这种类型的数据结构也称为二叉堆。
堆操作
下面将描述堆的一些重要操作及其算法。
堆化
堆化是从二叉树创建堆数据结构的过程。它用于创建最小堆或最大堆。
- 设输入数组为
初始数组 - 从数组创建完全二叉树
完全二叉树 - 从非叶子节点的第一索引开始，其索引由
n/2 - 1给出。
从第一个叶子节点开始 - 将当前元素
i设置为largest。 - 左子节点的索引由
2i + 1给出，右子节点的索引由2i + 2给出。
如果leftChild大于currentElement（即ith索引处的元素），则将leftChildIndex设置为 largest。
如果rightChild大于largest中的元素，则将rightChildIndex设置为largest。 - 交换
largest和currentElement
必要时交换 - 重复步骤 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- 将新元素插入树的末尾。
插入到末尾 - 堆化树。
对于最小堆，上述算法进行了修改，以便 parentNode 始终小于 newNode。
从堆中删除元素
最大堆删除算法
If nodeToBeDeleted is the leafNode
remove the node
Else swap nodeToBeDeleted with the lastLeafNode
remove noteToBeDeleted
heapify the array- 选择要删除的元素。
选择要删除的元素 - 将其与最后一个元素交换。
与最后一个元素交换 - 删除最后一个元素。
删除最后一个元素 - 堆化树。
对于最小堆，上述算法进行了修改，以便 childNodes 都大于 currentNode。
查看（查找最大/最小值）
查看操作返回最大堆中的最大元素或最小堆中的最小元素，而不删除节点。
对于最大堆和最小堆
return rootNode
提取最大/最小值
Extract-Max 在从最大堆中删除最大值节点后返回该节点，而 Extract-Min 在从最小堆中删除最小值节点后返回该节点。
Python、Java、C/C++ 示例
# 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)
// 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;
}// 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 算法
- 堆排序