堆堆排序及堆的相关操作

博主是一个大一刚刚放暑假的大学生，大学我们只学习了c语言，现在这么卷只学c语言肯定不够，所以博主打算从零开始恶补c++顺便写文章记录一下，另外博主这个暑假还想记录一些算法基础内容欢迎关注哦。这些是是一些算法的记录和整理总结笔记要是什么时候忘记了这个算法那个算法怎么做就重新来看看，在csdn上面发是为了利用网址来编写思维导图的话比! 较方便~~~如果大家想跟着我一起学习也可以关注我~或者给这个文章点赞~~~谢谢大家了~

• 堆
• • 可以把数组的连续的一段想象成完全二叉树：
  • 堆：是一个完全二叉树
  • 小根堆：子比父大 头为最小。
  • 堆操作：
  • • • 如何建立堆：
      • 如何建立大根堆和小根堆
      • • heapInsert:给一个数字把这个数字加进去形成堆
        • heapify:堆化操作
        • 在已经形成堆的有效区域内改一个数，如何变成一个堆
  • 堆排序
  • • 时间复杂度分析
    • • 人工建堆扩展O（N）复杂度
      • 堆排序题目
    • C++ STL - 优先队列实现堆
    • • 扩容怎么办？

size=7

位置关系：i位置

左孩子为2*i+1

右孩子为2*i+2

父亲为(i-1)/2

n个数的二叉树的高度是log n级别的

大根堆：父比子大 头为最大。

首先我们先建立一个数组！
比如这个吧

首先我们看我们之前补充的父节点和子节点的理论

位置关系：i位置
左孩子为2i+1
右孩子为2i+2
父亲为(i-1)/2

也就是说在任意位置上我们都可以访问它的左孩子右孩子和他的父亲。
这样的话就好办了！！
其实这个数组就是一个堆，而通过上面的这个每个位置上的关系就可以确定他这个位置上的父节点和子节点了，这是我们建立大根堆小根堆的基础

当我们把这个数组看做是堆之后呢就要考虑如何建立大根堆和小根堆了，这才是堆的应用内容
大根堆就是父节点比子节点的数大就叫做大根堆
小根堆就是父节点比子节点的数小就叫做小根堆
下面展示一下heapInsert操作

#include 

using namespace std;


void heapInsert(int *a , int index );//给一个数字，把这个数字加进去形成大根堆
void heapInsert(int *a , int index )
{
    while(a[index] > a[(index-1)/2])//换成小于就是小根堆
    {
        swap(a[index],a[(index-1)/2]);
        index=(index-1)/2;
    }
}



int main()
{
    int n;
    cin>>n;
    int a[n];
    for (int i = 0;i < n;i++)
    {
        cin>>a[i];
       heapInsert(a,i);//每在数组加一个数就可以把他加进去形成大根堆函数~
    }
    int d;
    //cin>>d;
    //heapify(a , d , n);
    for (int i = 0;i < n;i++)
    {
        cout< 

 可以看到这里他就变成一个大根堆了，这个操作可以在一个堆里任意插入一个数使加入数后依旧是堆
 
 
heapify:堆化操作 
有一个堆，在任意位置加一个数，在这个位置向下出溜
 
void heapify(int *a,int index,int heapSize);//从一个地方出发向下堆化的过程
void heapify(int *a,int index,int heapSize)
{
    int left = 2 * index+1;//定义左孩子
    while (left < heapSize)
    {
        int largest = left;
        if(left + 1 < heapSize)
            if(a[left] < a[left + 1])
                largest = left + 1;
        if(index > largest)
            break;
        swap(a[index],a[largest]);
        index = largest;
        left = 2 * index + 1;
    }
}

 
 
在已经形成堆的有效区域内改一个数，如何变成一个堆 
 
 
1.heapInsert
 2.heapify
 
 
 
堆排序 
代码：
 
#include 

using namespace std;


void heapInsert(int *a , int index );//给一个数字，把这个数字加进去形成大根堆
void heapInsert(int *a , int index )
{
    while(a[index] > a[(index-1)/2])
    {
        swap(a[index],a[(index-1)/2]);
        index=(index-1)/2;
    }
}

void heapify(int *a,int index,int heapSize);//从一个地方出发向下堆化的过程
void heapify(int *a,int index,int heapSize)
{
    int left = 2 * index+1;//定义左孩子

    while (left < heapSize)
    {
        int largest = left;
        if(left + 1 < heapSize)
            if(a[left] < a[left + 1])
                largest = left + 1;

        if(index > largest)
            break;
        swap(a[index],a[largest]);
        index = largest;
        left = 2 * index + 1;
    }
}

void heapSort (int *a , int array_lenth)
{
    //0,1 可以直接返回！
   if(array_lenth < 2)
   {
        return;
   }
   //数组堆化
   for (int i = 0;i < array_lenth; i++){
    heapInsert(a , i);
   }
   //堆排序
   int heapSize = array_lenth;
   swap(a[0],a[--heapSize]);//把0位置上的数（最大值）和末位置的数交换
   while(heapSize > 0)
   {
       heapify(a , 0 , heapSize);//heapSize-1后把最大的数剔除到外面剩余的数进行堆化
       swap(a[0],a[--heapSize]);//重复此操作
   }

}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for (int i = 0;i < n;i++)
    {
        cin>>a[i];
       //heapInsert(a,i);
    }
    int arr_len = sizeof(a) / sizeof(a[0]);
    heapSort(a , arr_len);
    for (int i = 0;i < n;i++)
    {
        cout< 
 
时间复杂度分析 
heapInsert、heapify：log n（因为完全二叉树的高度为log n）
 堆排序的时间复杂度：n log n （建大根堆和heapify都是nlogn）
 
 
人工建堆扩展O（N）复杂度 
   //数组堆化
   for (int i = 0;i < array_lenth; i++){
    heapInsert(a , i);
   }
 
这个时间复杂度可以减少
 方案：从右到左从下到上做heapify
 时间复杂度分析：
 T（N）=N/21 + N/42 + N/8*3…
 用我们高中学过的错位相减法就可以估计出时间复杂度：O（N）
 代码：
 
//数组堆化
  // for (int i = 0;i < array_lenth; i++){
    //heapInsert(a , i);
   //}O(N logN)
   for (int i = array_lenth - 1;i >= 0;i--){
    heapify(a , i , array_lenth ) //就是从右到左在数组中进行heapify！我自己也想到了
   }
   

 
 
堆排序题目 
 
 
 
思路：
 把前k个数用堆求出最小值！然后向后移一位，再弹出一个最小值最后没有了在排序移
 出就排好序了！
 时间复杂度为O（N*logK）
 
 
代码（用下面的STL来实现）：
 
    void heapQ (int *a, int k, int arr_len);
    void heapQ (int *a, int k, int arr_len)
    {
        priority_queue, greater > arr;
        int index = 0;
        for (;index <= min(k,arr_len); index++)
        {
            arr.push(a[index])
        }
        int i = 0;
        for (;index < arr_len; i++, index++ ){
            arr.push(a[index]);
            arr[i] = arr.pop();
            while(!a.empty()){
                a[i++] = arr.pop();
            }
            
        }
    }
 
 
C++ STL - 优先队列实现堆 

 优先队列就是堆
 
1.首先写好队列头文件
 
#include
 
2.定义一个int型、值小的数优先级高(先出队列)的队列-----小根堆
 
*最后的’’ 与‘>’间注意留空格
 
priority_queue, greater > a;
 
大根堆的定义：
 
priority_queue > a;
//priority_queue, less > a;
 
3.操作：
 往堆中加一个元素：
 
a.push(x);
 
弹出堆顶元素：
 
a.pop();
 
访问堆顶元素：
 
a.top();
 
堆的大小：
 
a.size();
 
判断堆是否为空：
 
a.empty();
 
 
扩容怎么办？ 
耗尽的时候就成倍的扩容。
 N个数的时候扩容就是扩容了log N水平的次数O（N*logN）扩容代价算上也是logN水平
 
 
 
有的时候，你必须手写堆，不然在更改一个数的时候，系统的算法会从头开始，会影响效率