二插堆的基本原理以及简单实现

堆（Heap）

一、堆的基本概念

1. 定义

• 二叉堆是一种完全二叉树，它满足堆属性：
  • 最大堆：每个节点的值都大于或等于其子节点的值
  • 最小堆：每个节点的值都小于或等于其子节点的值

2. 特点

• 二、二叉堆的特点

  1. 完全二叉树：除了最后一层，其他层都是满的，最后一层从左到右填充
  2. 堆属性：父节点和子节点之间保持特定的大小关系
  3. 数组表示：可以用数组高效存储，不需要指针

二、堆的数组表示

对于下标为 i 的节点：

• 父节点：parent(i) = (i-1)/2
• 左子节点：left(i) = 2*i + 1
• 右子节点：right(i) = 2*i + 2

堆的相关操作

创建堆的类型

1. 包括堆的数组

2. 堆的类型(最大堆,最小堆)

3. 获取节点的父节点,左孩子,右孩子

class Heap { public: vector<int> heap; bool isMaxHeap; // true表示最大堆, false表示最小堆 // 获取父节点索引 int parent(int index) { return (index - 1) / 2; } // 获取左孩子索引 int leftChild(int index) { return 2 * index + 1; } // 获取有孩子索引 int rightChild(int index) { return 2 * index + 2; } };

上浮（Heapify Up）

1. 上浮操作用于在堆中插入新元素后，恢复堆的性质。

2. 当我们向堆的末尾添加一个新元素时，可能会破坏堆的堆序性（父节点大于/小于子节点）。

3. 上浮操作通过不断比较新元素与其父节点，必要时交换它们，直到堆性质恢复。

void heapifyUp(int index) { while (index > 0) { int parent = (index - 1) / 2; // 最大堆：如果当前节点大于父节点，交换 // 最小堆：如果当前节点小于父节点，交换 if (compare(heap[index], heap[parent])) { swap(heap[index], heap[parent]); index = parent; } else { break; } } }

下沉（Heapify Down）

1. 下沉操作用于移除堆顶元素后，恢复堆的性质。

2. 当我们移除堆顶元素时，通常将最后一个元素移到堆顶，然后通过下沉操作将其调整到合适位置，恢复堆性质。

void heapifyDown(int index) { int size = heap.size(); while (true) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int target = index; // 找到需要交换的子节点 if (leftChild < size && compare(heap[leftChild], heap[target])) { target = leftChild; } if (rightChild < size && compare(heap[rightChild], heap[target])) { target = rightChild; } // 如果需要交换，继续下沉 if (target != index) { swap(heap[index], heap[target]); index = target; } else { break; // 堆性质已满足 } } }

插入操作

1. 插入操作向堆中添加新元素。首先将元素添加到数组末尾.
2. 然后执行上浮操作将其调整到正确位置。

// 插入元素 void push(int value) { heap.push_back(value); heapifyUp(heap.size() - 1); }

删除堆顶元素

1. 检查堆是否为空
2. 保存堆顶元素
3. 将最后一个元素移到堆顶
4. 删除最后一个元素
5. 如果堆不为空，对堆顶执行下沉操作

void pop() { if (heap.empty()) { cout << "堆为空，无法删除！" << endl; return; } heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) { heapifyDown(0); } }

获取堆顶元素

1. 检查堆是否为空
2. 返回数组的第一个元素

// 获取堆顶元素 int top() { if (heap.empty()) { cout << "堆为空！" << endl; return -1; } return heap[0]; }

完整代码

class Heap { public: vector<int> heap; bool isMaxHeap; // true表示最大堆, false表示最小堆 // 比较函数 bool compare(const int& a, const int& b) { return isMaxHeap ? a > b : a < b; } // 获取父节点索引 int parent(int index) { return (index - 1) / 2; } // 获取左孩子索引 int leftChild(int index) { return 2 * index + 1; } // 获取有孩子索引 int rightChild(int index) { return 2 * index + 2; } // 上浮操作 void heapifyUp(int index) { while (index > 0) { int parent = (index - 1) / 2; if (compare(heap[index], heap[parent])) { swap(heap[index], heap[parent]); index = parent; } else { break; } } } // 下沉操作 void heapifyDown(int index) { int size = heap.size(); while (true) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int target = index; // 找到当前节点、左子节点、右子节点中最符合堆性质的节点 if (leftChild < size && compare(heap[leftChild], heap[target])) { target = leftChild; } if (rightChild < size && compare(heap[rightChild], heap[target])) { target = rightChild; } // 如果当前节点不是最大的/最小的，交换并继续下沉 if (target != index) { swap(heap[index], heap[target]); index = target; } else { break; } } } // 构造函数 Heap(bool maxHeap = true) : isMaxHeap(maxHeap) {} // 从数组建堆的构造函数 Heap(const vector<int>& arr, bool maxHeap = true) : isMaxHeap(maxHeap) { heap = arr; // 从最后一个非叶子节点开始建堆 for (int i = heap.size() / 2 - 1; i >= 0; i--) { heapifyDown(i); } } // 插入元素 void push(int value) { heap.push_back(value); heapifyUp(heap.size() - 1); } // 删除堆顶元素 void pop() { if (heap.empty()) { cout << "堆为空，无法删除！" << endl; return; } heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) { heapifyDown(0); } } // 获取堆顶元素 int top() { if (heap.empty()) { cout << "堆为空！" << endl; return -1; } return heap[0]; } // 堆是否为空 bool empty() { return heap.empty(); } // 获取堆大小 int size() { return heap.size(); } // 获取堆类型 string getType() { return isMaxHeap ? "最大堆" : "最小堆"; } };