数据结构小记【Python/C++版】——堆结构篇

一，基础概念

堆结构是一种完全二叉树。

完全二叉树的结构特点是，除了最后一层，其他层的节点数都是满的，最后一层的节点靠左排列。

堆结构分为两种类型：最小堆和最大堆。

最小堆：父节点元素的值都小于或等于子节点，根是树中的最小元素。

最大堆：父节点元素的值都大于或等于子节点，根是树中的最大元素。

堆结构常应用于排序和生成优先级队列。

最小堆和最大堆图示：

二，堆结构的基本操作

1.堆结构的表示

堆结构经常使用一个数组来实现，树的根是数组的第一个元素。

数组属于顺序存储，比使用了指针的链式存储节省空间，且不需要为左/右子节点指针分配内存空间。

使用数组表示堆结构和二叉树中的方法一样，假如堆结构中的一个节点，索引为N，可以得到：

父节点的索引：N // 2(整除)

左子节点的索引：N * 2 或 N * 2 + 1

右子节点的索引：N * 2 + 1 或 N * 2 + 2

图示样例：

2.数组的堆化(Heapify)

如果往堆中的根节点或者叶子节点中分别删除元素或者添加元素，则会改变堆中的元素大小顺序，使堆变成排列无序的数组。因此，堆化指的是使普通数组变得有序化，从而形成堆。

堆化的本质操作其实就是数组中元素的互换位置。

图示样例：

图中原有的数组为：[20, 4, 8, 10, 5, 7, 6, 2, 9, 1]，目前还不算一个标准的堆结构。

图中应该生成一个最大堆——所有节点的元素值大于或等于子节点的元素值。节点2的数值为4，小于子节点的数值。开始进行数组的堆化，首先将节点2与节点4进行元素互换，使节点2位置的值大于节点4位置的值。后面的子节点如果遇到上述情况则继续互换元素，直到生成一个标准的堆结构。

步骤一：交换元素4和元素10，生成新的数组。

步骤二：交换元素4和元素9，最终生成标准的最大堆。

堆化的伪代码

MAX-HEAPIFY(A, i)
left = 2i
right = 2i + 1

// checking for largest among left, right and node i
largest = i
if left <= heap_size
  if (A[left] > A[largest])
    largest = left

if right <= heap_size
  if(A[right] > A[largest])
    largest = right

//node is not the largest, we need to swap
if largest != i 
  swap(A[i], A[largest])
  //chlid after swapping might be violating max-heap property
  MAX-HEAPIFY(A, largest)

3.堆结构中插入节点(最大堆)

操作步骤：

step.01: 如果没有节点，创建一个新节点。如果已有节点，在末尾插入新节点(从左到右的最后一个节点)。

step.02: 执行数组的堆化。

图示样例：

原始数组： [9, 4, 5, 1, 3, 2]

插入的元素：7

最终结果： [9, 4, 7, 1, 3, 2, 5]

4.堆结构中删除节点(最大堆)

操作步骤：

step.01: 被删除的节点是叶子节点，直接在数组的尾部删除。被删除的节点不是叶子节点，将被删除的节点与末尾叶子节点交换位置，在数组的尾部删除该节点。

step.02: 执行数组的堆化。

图示样例：

原始数组： [9, 4, 7, 1, 3, 2, 5]

删除的元素：4

最终结果： [9, 5, 7, 1, 3, 2]

三，代码实现

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((len(array) // 2) - 1, -1, -1):
        heapify(array, len(array), 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)

if __name__ == "__main__":
    arr = []
    insert(arr, 9)
    insert(arr, 4)
    insert(arr, 5)
    insert(arr, 1)
    insert(arr, 3)
    insert(arr, 2)

    print("Max-Heap array: " + str(arr))

    insert(arr, 7)
    print("After Insert 7: " + str(arr))

    deleteNode(arr, 4)
    print("After Delet 4: " + str(arr))

运行结果：

Max-Heap array: [9, 4, 5, 1, 3, 2]
After Insert 7: [9, 4, 7, 1, 3, 2, 5]
After Delet 4: [9, 5, 7, 1, 3, 2]

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, 9);
    insert(heapTree, 4);
    insert(heapTree, 5);
    insert(heapTree, 1);
    insert(heapTree, 3);
    insert(heapTree, 2);
    cout << "Max-Heap array: ";
    printArray(heapTree);
    cout << "After Insert 7: ";
    insert(heapTree, 7);
    printArray(heapTree);

    cout << "After Delete 4: ";
    deleteNode(heapTree, 4);
    printArray(heapTree);
}

运行结果：

Max-Heap array: 9 4 5 1 3 2
After Insert 7: 9 4 7 1 3 2 5
After Delete 4: 9 5 7 1 3 2