C++实现二叉堆堆排序 |21xrx.com

C++实现二叉堆堆排序

2023-07-01 12:22:01 深夜i -- --

C++ 二叉堆堆排序

二叉堆是一种计算机科学中经常被使用到的数据结构。它是一种完全二叉树，并且有一个重要的性质：任意一个节点的值都大于（或小于）其子节点的值。这种性质使得二叉堆的结构在排序算法中非常有用。本文将介绍如何使用C++实现二叉堆的堆排序。

首先，我们需要定义一个二叉堆数据结构。二叉堆有两种类型：最大堆和最小堆。在此，我们使用最大堆。最大堆的定义如下：


class MaxHeap {
  private:
    int *data;
    int size;
    int capacity;
    void percolateDown(int i); //向下调整
    void percolateUp(int i); //向上调整
  public:
    MaxHeap(int cap) {
      data = new int[cap + 1]; //注意下标从1开始，因此数组需要开大一位
      size = 0;
      capacity = cap;
    }
    ~MaxHeap() {
      delete[] data;
    }
    void insert(int num); //插入元素
    int popMax(); //弹出最大元素
    bool isEmpty() {
      return size == 0;
    }
    int getSize() {
      return size;
    }
};

在以上代码中，我们实现了一个最大堆数据结构，其中包含了向下调整和向上调整两个操作，用于维护二叉堆的性质。其中，insert()函数用于向堆中插入元素，而popMax()函数用于弹出最大的元素。

接下来，我们可以使用二叉堆进行堆排序。堆排序使用的是选择排序的思想，首先将整个数组构建成一个二叉堆，然后将二叉堆中的最大元素弹出到数组的末尾，然后重新维护二叉堆的性质，如此反复进行，直到整个数组有序为止。

下面是堆排序的C++代码实现：


void heapSort(int arr[], int n) {
  MaxHeap heap(n);
  for(int i = 0; i < n; i++) {
    heap.insert(arr[i]);
  }
  for(int i = n - 1; i >= 0; i--) {
    arr[i] = heap.popMax();
  }
}

在以上代码中，我们首先创建了一个最大堆，然后将给定的数组中的所有元素都插入到这个堆中。接着，我们开始进行堆排序的核心步骤：将堆中的最大元素依次弹出，放到指定的位置，并且重新维护堆的性质。最终，得到的就是一个有序的数组。

总结起来，二叉堆是一种非常有用的数据结构，它可以被广泛应用于各种排序算法中。本文介绍了如何使用C++实现一个最大堆，并且使用堆排序对一个无序数组进行排序的方法。在实际工作中，如果需要对大规模数据进行排序，堆排序的时间复杂度O(nlogn)将会是一个非常优秀的选择。

上一篇: idea打包java可执行jar包

下一篇: Visual C++ 卸载会影响哪些部分？

评论区

()

相似文章