21xrx.com
2025-03-27 07:55:41 Thursday
文章检索 我的文章 写文章
C++实现堆 - 简单易懂，快速上手
2023-07-05 02:51:29 深夜i     15     0
C++ 堆 简单易懂 快速上手 实现

堆是一种常见的数据结构，常被用来处理优先级相关的问题。C++作为一种高级编程语言，与很多其它语言相比，实现堆的过程要相对简单很多。今天我们就来聊一聊如何使用C++来实现堆。

首先，我们需要知道什么是堆。堆是一种特殊的树形数据结构，其中每个结点的值都比其子节点的值大（或小）。堆有两种类型：大根堆和小根堆。如果每个结点的值都比其子节点的值大，则为大根堆；如果每个结点的值都比其子节点的值小，则为小根堆。

接下来，我们就来看看如何使用C++来实现堆。

首先，我们需要定义一个堆结构体。在结构体中，我们定义了一个整型数组和一个表示堆大小的变量。

struct Heap {
  int arr[100];
  int size;
};

接下来，我们来定义一些堆基本操作，例如查找父节点、查找左子节点以及查找右子节点。

int parent(int i) {
  return (i - 1) / 2;
}
int leftChild(int i) {
  return (2 * i) + 1;
}
int rightChild(int i) {
  return (2 * i) + 2;
}

接下来，我们就来看看如何实现添加元素到堆中。为了保证堆的结构始终正确，我们需要进行一些操作。我们需要先将新加入的元素加入到数组的最后一个位置。然后，我们需要一个循环来向上移动这个元素，直到其找到了自己的合适位置。在这个过程中，我们可以通过与其父节点比较大小来确定它应该在堆的哪个位置。

void addToHeap(Heap* heap, int val) {
  heap->arr[heap->size++] = val;
  int i = heap->size - 1;
  while (i != 0 && heap->arr[parent(i)] < heap->arr[i]) {
    swap(heap->arr[parent(i)], heap->arr[i]);
    i = parent(i);
  }
}

下一个需要实现的操作是从堆中移除元素。删除堆顶元素时，我们需要先找到堆顶元素，然后将堆顶元素与数组最后一个元素交换位置，最后从堆中移除数组中的最后一个元素。接着，我们需要比较新的堆顶元素和其子节点的大小，确保堆的结构始终正确。

void removeFromHeap(Heap* heap) {
  heap->arr[0] = heap->arr[heap->size - 1];
  heap->size--;
  heapify(heap, 0);
}
void heapify(Heap* heap, int i) {
  int L = leftChild(i);
  int R = rightChild(i);
  int max = i;
  if (L < heap->size && heap->arr[L] > heap->arr[max]) {
    max = L;
  }
  if (R < heap->size && heap->arr[R] > heap->arr[max]) {
    max = R;
  }
  if (max != i) {
    swap(heap->arr[i], heap->arr[max]);
    heapify(heap, max);
  }
}

最后，我们来看看如何打印出堆的元素。我们只需要循环遍历数组，按顺序打印出数组中的每一个元素即可。

void printHeap(Heap* heap) {
  for (int i = 0; i < heap->size; i++) {
    cout << heap->arr[i] << " ";
  }
  cout << endl;
}

至此，我们已经完成了如何使用C++来实现堆的所有内容。此时你再来看看整个过程，它其实是非常简单的，并且可以让你快速将堆的思想应用到编程中。随着你的编程技巧增强，你还可以跟据需要对这些操作进行扩展和改进。

  
  

评论区