堆的基本操作

@[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;


}
*/