标签搜索

目 录CONTENT

文章目录

堆的基本操作.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 4,633 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

堆的基本操作

@[toc]

一、 堆的概念及结构:

  •  1.如果有一个关键码的集合K = {k0,k1, k2,...,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2i+1 Ki<= K2i+2 (Ki >= K2i+1 Ki >= K2i+2) i = 0,1,2...,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

  •  2.堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;

  • 堆总是一棵完全二叉树

  •  3.事例:

在这里插入图片描述

二、堆的实现:

  •  1.堆的向下调整算法:

  • 给出一个数组,逻辑上看作一颗完全二叉树。通过从根结点开始的向下调整算法可以把数组调整成一个大堆或者一个小堆。

  • 堆的向下调整算法的前提是:左右子树必须也是一个堆 ,才能进行调整。

    int a[] = {27,15,19,18,28,34,65,49,25,37};
    在这里插入图片描述

  •  2.堆的创建:

  • 下面给出一个数组,这个数组逻辑上看作一个完全二叉树,但还不是一个堆,现在得需要通过向下调整算法,把它构成一个堆。

  • 所以得从倒数第一个非叶子节点的子树开始调整,就可以构成一个堆
    在这里插入图片描述

  •  3.堆的插入:

  • 把待插入的数值直接放在堆的尾,进行一次向上调整即可

在这里插入图片描述

  •  4.堆的删除:
  • 删除的规则是将堆顶的数据和最后一个数据进行交换,删除最后一个元素,最后进行一次向下调整即可

三、代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* _a;
      int _size;
        int _capacity;

}Heap;

void PPrint(int * arr, int len);

void Down(int* arr, int len, int parent);

void Up(int * arr, int child);

void HeapUp(Heap* hp, int index);

void HeapDown(Heap* hp, int index);

void Print(Heap * hp);

// 堆的构建
 void HeapCreate(Heap* hp, HPDataType* a, int n);
 // 堆的销毁
 void HeapDestory(Heap* hp);
 // 堆的插入
 void HeapPush(Heap* hp, HPDataType x);
 // 堆的删除
 void HeapPop(Heap* hp);
 // 取堆顶的数据
 HPDataType HeapTop(Heap* hp);
 // 堆的数据个数
 int HeapSize(Heap* hp);
 // 堆的判空
 int HeapEmpty(Heap* hp);

 // 对数组进行堆排序
 void HeapSort(int* a, int n);
 

#include"heap.h"

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
  hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n);
  memcpy(hp->_a, a, sizeof(HPDataType)*n);
  hp->_size = n;
  hp->_capacity = n;

  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    HeapDown(hp, i);
  }

}
// 堆的销毁
void HeapDestory(Heap* hp)
{
  free(hp->_a);
  hp->_a = nullptr;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
  if (hp->_size == hp->_capacity)
  {
    hp->_a = (HPDataType*)realloc(hp->_a ,hp->_capacity * 2 * sizeof(HPDataType));
    hp->_capacity *= 2;
  }

  hp->_a[hp->_size] = x;
  hp->_size++;

  HeapUp(hp, hp->_size - 1);
}

// 堆的删除
void HeapPop(Heap* hp)
{
  if(hp->_a == nullptr)
  {
    return ;
  }

  swap(hp->_a [0],hp->_a [hp->_size -1]);
  hp->_size --;
  HeapDown(hp,0);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
  if(hp->_a ==nullptr)
  {
    return -1;
  }
  return hp->_a [0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
  return hp->_size ;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
  if(hp->_size ==0)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

// 对数组进行堆排序
void HeapSort(int* a, int n)
{
  for (int i = (n - 2) / 2; i >= 0; i--)
  {
    Down(a, n, i);
  }
  /*
     for (int i = 0; i < n ; i++)
     {
     swap(a[0], a[n - 1 - i]);

     Down(a, n - i, 0);
     }
     */
  int end = n - 1;
  while (end)
  {
    swap(a[0], a[end]);
    Down(a, end, 0);
    end--;
  }

}

void Up(int * arr, int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if(child>0&& arr[parent]>arr[child])
    {
      swap(arr[child],arr[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

void PPrint(int * a,int n)
{
  for (int i = 0; i < n; i++)
  {
    cout << a[i] << " ";

  }
  cout << endl;
}
void HeapDown(Heap* hp, int index)
{
  HPDataType child = index * 2 + 1;
  while (child < hp->_size)
  {
    if ((index * 2 + 2) < hp->_size && hp->_a[child] > hp->_a[child + 1])
    {
      child = child + 1;
    }

    if (hp->_a[index] > hp->_a[child])
    {
      swap(hp->_a[index], hp->_a[child]);
      index = child;
      child = index * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

void HeapUp(Heap* hp, int index)
{
  HPDataType parent = (index - 1) / 2;
  while (index > 0)
  {
    if (hp->_a[index] < hp->_a[parent])
    {
      swap(hp->_a[index], hp->_a[parent]);
      index = parent;
      parent = (index - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
void Print(Heap * hp)
{
  for(int i = 0; i < hp->_size; i++)
  {
    cout << hp->_a[i] << " ";
  }
  cout << endl;
}

void Down(HPDataType* arr, int len ,int parent)
{
   int child = parent * 2 + 1;
  while (child<len)
  {
    if (child + 1 < len && arr[child] > arr[child + 1])
    {
      //swap(arr[child], arr[child + 1]);
      child = child + 1;
    }
    if(arr[parent]>arr[child])
    {
      swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}


#include"heap.h"

void test()
{
  Heap hp;
  int arr[10] = { 2,8,7,6,5,4,3,2,1,0  };
  HeapCreate(&hp, arr, 10);
  Print(&hp);
  HeapPush(&hp,999); 
  Print(&hp);
  HeapPop(&hp);
  Print(&hp);
  cout<<HeapEmpty(&hp)<<endl;
  cout<<HeapTop(&hp)<<endl;
  //HeapSort(arr, 10);
  //PPrint(arr,10);

}


int main()
{

  test();
  system("pause");
  return 0;

}


/*
#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;

int main()
{
#if 1
int n;
//while (cin >> n)
cin >> n;
{
vector<string>ret;
string str;
stack<int>s;
n = n + 1;
while (n)
{
getline(cin,str);
ret.push_back(str);
n--;
}

for (int i = 0; i < ret.size(); i++)
{
if (ret[i][0] == 'P')
{
s.push(ret[i][1]);
}
if (ret[i][0] == 'O' && !s.empty())
{
s.pop();
}
if (ret[i][0] == 'A')
{
if (s.empty())
{
printf("E\n");
}
else
{
printf("%d\n", s.top());
}
}
}
}
#endif
#if 0
string str;
vector<string>ret;
int i = 5;
while (i)
{
getline(cin, str);
i--;
}
for (int i = 0; i < ret.size(); i++)
{
cout << ret[i] << endl;
}
#endif
system("pause");
return 0;


}
*/

0

评论区