目录

一，二叉堆

二，堆的调整

三，堆的创建

四，堆排序

五，堆元素更新

六，堆的插入

一，二叉堆

二叉堆是用数组实现的完全二叉树，也就是说物理结构是数组，逻辑结构是完全二叉树。

二叉堆分2种，最大堆和最小堆。

最大堆指的是，任何一个结点都比它的两个子结点（或1个或0个）要大，最小堆同理。

本文以最大堆为例进行展示。

二，堆的调整

堆的调整指的是，给出一个完全二叉树，除了根结点之外，左子树是二叉堆，右子树是二叉堆，现在要调整元素位置，让整个树成为二叉堆。

其实就是把堆顶元素不停的往下塞，塞到合适的位置就停止了。

实现代码：

      template<typename T>
      bool cmp(T a, T b)
      {
         return a < b; //最大堆
      }
      template<typename T>
      void exchange(T* a, T* b)
      {
          T tmp = *a;
          *a = *b;
          *b = tmp;
      }
      int LeftChild(int id)
      {
         return id * 2;
      }
      int RightChild(int id)
      {
         return id * 2 + 1;
      }
      int Parent(int id)
      {
         return id/2;
      }
      template<typename T>
      void AdjustHeap(T* arr, int rootId, int size)
      {
         int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
         if (left < size && cmp(arr[largest], arr[left]))largest = left;
         if (right < size && cmp(arr[largest], arr[right]))largest = right;
         if (largest == rootId)return;
         exchange(arr + rootId, arr + largest);
         AdjustHeap(arr, largest, size);
      }
  
 

时间复杂度：O（h），其中h是二叉堆的高度，h=Θ（log n），其中n=size，表示所有结点数目

三，堆的创建

给出一个数组，现在要交换元素位置，使得它变成一颗二叉堆。

实现代码：

      template<typename T>
      void InitHeap(T* arr, int size)
      {
         for (int i = size / 2; i >= 0; i--)AdjustHeap(arr, i, size);
      }
  
 

原理：因为是完全二叉树，所以最后一层的结点数目小于总数的一半，也就是说，从size/2到0覆盖了除掉最后一层之外的所有结点。

时间复杂度：Θ（n），其中n=size，表示所有结点数目

四，堆排序

算法思路：

先构建二叉堆，于是数组第一个元素就是最大元素，把它和最后一个元素交换，

对于剩下的n-1个元素，直接调用AdjustHeap即可再次变成堆，于是得到了这n-1个元素里面的最大值，

依次类推，最后就变成增序的数组了。

      template<typename T>
      void HeapSort(T* arr, int size)
      {
         InitHeap(arr, size);
         for (int i = size - 1; i > 0; i--) {
             exchange(arr + i, arr);
             AdjustHeap(arr, 0, i);
          }
      }
  
 

时间复杂度：O（n log n）

五，堆元素更新

      template<typename T>
      void HeapIncrese(T* arr, int size, int id, T newValue)
      {
          arr[id] = newValue;
         while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
             exchange(arr + id, arr + Parent(id));
              id = Parent(id);
          }
      }
      template<typename T>
      void HeapDecrese(T* arr, int size, int id, T newValue)
      {
          arr[id] = newValue;
         AdjustHeap(arr, id, size);
      }
      template<typename T>
      void HeapChange(T* arr, int size, int id, T newValue)
      {
         if (cmp(arr[id], newValue))HeapIncrese(arr, size, id, newValue);
         else HeapDecrese(arr, size, id, newValue);
      }
  
 

六，堆的插入

      template<typename T>
      void HeapInsert(T* arr, int &size,T value)
      {
         HeapIncrese(arr,size+1,size,value);
          size++;
      }
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/113484808