欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浅析堆的基本操作以及堆排序

程序员文章站 2024-02-11 21:17:04
...

一、堆的基本介绍

1、堆的概念
堆是一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组的对象。堆满足以下的性质
(1)堆中某个节点的值总是不大于或不小于其父节点的值
(2)堆总是一棵完全二叉树

2、堆的分类
(1)最小堆:任一节点的关键码均小于等于它的左右孩子的关键码,位于堆顶的节点的关键码最小(向上调整)
(2)最大堆:任一节点的关键码均大于等于它的左右孩子的关键码,位于堆顶的节点的关键码最大(向下调整)

3、堆中下标为i的节点的特点
因为堆是存储在下标为0 开始计数的数组中,因此在堆中给定下标为i的节点时:
(1)如果i=0,节点i为根节点, 没有双亲节点; 否则节点i的双亲节点为节点(i-1)/2
(2)如果2*i+1>n-1,则节点i无左孩子,否则节点i的左孩子为节点2*i+1
(3)如果2*i+2>n-1,则节点i无右孩子,否则节点i的右孩子为节点2*i+2

二、堆的基本操作
1、堆的创建

给定数组:int array = {23,14,8,90,45,70,66}
先将数组用二叉树表示出来:
浅析堆的基本操作以及堆排序
因为现在还是二叉树,不算意义上的堆,所以我们需要把它调整成为最小堆or最大堆
(1)向下调整:(最大堆)
我们可以将调整一整棵树细化成为调节树的左右子树为最小堆,再去调节以左右子树为双亲节点的左右子树……,一直到整棵都被调整完。具体过程如下:

* a、找到树中最后一个非叶子节点,然后开始调整
* b、比较其左右孩子节点的大小,找出较大的孩子节点
* c、用较大的孩子节点去和它的双亲作比较。倘若孩子节点大于双亲节点,则交换双亲和孩子节点,并更新双亲节点和孩子节点;若小于,则结束此次的调整。

调整上图的二叉树为最大堆,如下图所示:
浅析堆的基本操作以及堆排序

//向下调整(最大堆)
      void _AdjustDown(size_t parent)
      {
            //用child标记左右孩子中最小的孩子,默认左孩子是最小的
            size_t child = parent * 2 + 1;
            size_t size = _array.size();
            Compare com;   //比较器                             //(小于的参数放在前面)
            while (child < size)
            {
                  //找左右孩子中最小的
                  if (child + 1 < size && com(_array[child + 1], _array[child]))   //左右孩子之间比较
                  {
                        child = child + 1;
                  }
                  //用大孩子和双亲去比较
                  if (com(_array[child], _array[parent]))
                  {
                        swap(_array[parent], _array[child]);
                        //调整子树
                        parent = child;
                        child = parent * 2 + 1;
                  }
                  else
                        break;
            }
      }
注:这里也可不用比较器

(2)向上调整(最小堆)
向上调整的过程基本上和向下调整差不多,就只是比较大小的时候是相反的,这里就不过多赘述了。直接上代码吧!!!

//向上调整(最小堆)
      void _AdjustUp(size_t child)
      {
            size_t parent = (child - 1) / 2;
            while (child > 0)
            {
                  if (_array[child] > _array[parent])
                  {
                        swap(_array[child], _array[parent]);
                        parent = child;
                        child = (parent - 1) / 2;
                  }
                  else
                        break;
            }
      }

2、插入
往堆里插入元素就是在已经调整好的最大堆or最小堆的最后面插入元素,但插入之后可能会破会堆的结构,因此需要将堆重新调整,使其满足最大堆or最小堆。
浅析堆的基本操作以及堆排序

//尾插
      void Push(const T& data)
      {
            _array.push_back(data);
            if (_array.size()>1)
            {
                  _AdjustUp(_array.size()-1);
            }
      }

3、堆的删除
堆的删除就是从堆中删除堆顶元素。删除堆顶元素之后,用堆的最后一个叶子结点去填补刚被删除的堆顶元素,并将堆的实际元素减一。但用最后一个元素取代堆顶的元素之后可能会破坏堆的平衡,因此需要将堆重新调整,使其满足最大堆or最小堆。
浅析堆的基本操作以及堆排序

//删除堆中元素
      void Pop()
      {
            if (Empty())
            {
                  return;
            }
            size_t last = _array.size() - 1;
            swap(_array[0], _array[last]);
            _array.pop_back();
            if (_array.size()>1)
            {
                  _AdjustDown(0);
            }
      }

4、堆排序(一种不稳定的排序算法)
(1)先创建好堆(见上述具体过程)。升序排列时创建大堆,降序排列时创建小堆
(2)排序(就是让刚才建好的大堆or小堆变得有序起来)。具体过程如下

* a、把堆顶元素array[0]和堆的最后一个元素交换
* b、最堆元素个数减一(这样就是为了避开刚交换的元素去调整剩下的元素)
* c、当交换元素之后,堆肯定会不满足最堆的定义,此次需要调整节点

浅析堆的基本操作以及堆排序
**

注:重复上图的过程一直到堆排列有序

**

//调整堆
      void AdjustHeap(int array, size_t size, size_t parent)
      {
            //标记最大的孩子,默认左孩子最大
            size_t child = parent * 2 + 1;
            while (child < size)
            {
                  //找左右孩子中最大的孩子
                  if (child + 1 < size && array[child + 1] > array[child])
                  {
                        child = child + 1;
                  }
                  //用最大的孩子去检测双亲
                  if (array[parent] < array[child])
                  {
                        swap(array[parent], array[child]);
                        parent = child;
                        child = parent * 2 + 1;
                  }
                  else
                        return;
            }
      }

//堆排序
      void HeapSort(int* array, size_t size)
      {
            //创建堆
            //倒数第一个非叶子节点的位置
            int root = (size - 2) / 2;
            for (; root >= 0; --root)
            {
                  AdjustHeap(array, size, root);
            }
            //堆排序
            for (int i = 0; i < size; i++)
            {
                  swap(array[0], array[size - i - 1]);
                  AdjustHeap(array[0], size - i - 1, 0)
            }
      }

5、堆的应用
(1)堆的应用之大数据处理:从1000亿个数据中找出最大的前k个数
思路:

* a、先取出k个数据
* b、将去取出的数据建为小堆(建立小堆的话,堆顶元素就是最大的,这样      就可以用比堆顶大的元素去交换,但倘若建大堆的话,堆顶元素就是最大的,这样后面的数据元素就会进不去,这样只会找到一个最大的元素)
* c、将剩下的数据依次和堆顶比较,若比堆顶大,则去替换堆顶,然后调整堆。周而复始,依次进行