树结构_大顶堆

树结构 - 大顶堆结构及其操作

结构 HeapStruct - MaxHeap

1. 存放结点数据的数组Elements，从1位置开始存，0位置放哨兵
2. 数组元素个数Size
3. 数组最大容量Capacity

创建

1. 动态申请堆空间
2. 动态申请堆的数组空间大小为MaxSize
3. 初始化大小及容量
4. 在堆的数组第0个元素存入哨兵，最大或最小值

堆是否为空

1. 判断堆的size是否为0

堆是否已满

1. 判断堆的size是否等于堆的容量

将元素item插入堆

1. 判断堆是已满
2. 找到堆数组的最后位置++H->Size
3. 遍历数组最末位元素结点至根结点，与插入值item比较，直到item小于父结点
4. 如果插入的元素item大于它的父结点，则需要换位，并找到新插入点的合适位置
5. 遍历结束找到新结点item有位置i

删除堆的根结点，最大元素

1. 判断堆是否为空
2. 找到堆的最大元素即根结点
3. 将堆数组最末位元素Temp拎出增补空缺
4. 遍历整个堆p*2<size,找到最末位结点的新位置
5. 比较左、右子树的大小，取较大者
6. 如果最末位元素Temp大于左、右子树，则不处理，否则左、右子树较大者覆盖父结点
7. 遍历结束，找到Temp位置parent，插入元素

下滤：将H->Element[P]为根的子堆调整为最大堆

1. 找到位置P对应的值X
2. 遍历以P为根结点的整棵树
3. 取结点左、右子树较大者
4. 如果父结点X的值比子结点大，不处理，否则父子换位
5. 遍历结束，找到P对应的位置Parent，插入原来的根结点值

将完全二叉树调整为最大堆

1. 从最后一个有子孩子的结点(size/2)向前进行下滤

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

#define MAXDATA 1000
#define ERROR -1;

typedef int ElementType;;
typedef struct HeapStruct *MaxHeap;// 大顶堆
struct HeapStruct {
    //1.存放结点数据的数组，从1位置开始存，0位置放哨兵
    ElementType *Elements;
    // 2.数组元素个数
    int Size;
    // 3.数组最大容量
    int Capacity;
};

bool IsEmpty(MaxHeap H);

bool IsFull(MaxHeap H);

// 创建
MaxHeap Create(int MaxSize) {
    // 1.动态申请堆空间
   MaxHeap H = (MaxHeap) malloc(sizeof(struct HeapStruct));
   // 2.动态申请堆的数组空间大小为MaxSize
   H->Elements = (ElementType) malloc(sizeof(ElementType) * MaxSize);
   // 3.初始化大小及容量
   H->Size = 0;
   H->Capacity = MaxSize;
   // 4.在堆的数组第0个元素存入哨兵，最大或最小值
   H->Elements[0] = MAXDATA; //建立哨兵
   return H;
}

// 堆是否为空
bool IsEmpty(MaxHeap H) {
    // 1.判断堆的size是否为0
   return H->Size == 0;
}

// 堆是否已满
bool IsFull(MaxHeap H) {
    // 1.判断堆的size是否等于堆的容量
   return H->Size == H->Capacity;
}

//将元素item插入堆
void Insert(MaxHeap H, ElementType item) {
   int i;
   // 1.判断堆是已满
   if (IsFull(H)) {
       printf("最大堆已满");
       return;
   }
   // 2.找到堆数组的最后位置++H->Size
   i = ++H->Size; // 新插入的元素加在堆的最后一个位置
   // H->Element[0]为最大元素，为哨兵结点，H->Elements[i / 2] < item可控制循环结点
   // 3.遍历数组最末位元素结点至根结点，与插入值item比较，直到item小于父结点
   for (; H->Elements[i / 2] < item; i /= 2) {
       // 4.如果插入的元素item大于它的父结点，则需要换位，并找到新插入点的合适位置
       H->Elements[i] = H->Elements[i / 2];
   }
   // 5.遍历结束找到新结点item有位置i
   H->Elements[i] = item;
}

/**
* 删除堆中的最大元素，即根结点
* 每层比较 根结点 左+右子结点，以及最后一个元素结点
* @param H
* @return
*/
ElementType DeleteMax(MaxHeap H) {
   ElementType MaxItem, Temp;
   int Parent, Child;
   // 1.判断堆是否为空
   if (IsEmpty(H)) {
       printf("最大堆为空");
       return ERROR;
   }
   // 2.找到堆的最大元素即根结点
   MaxItem = H->Elements[1];
   // 3.将堆数组最末位元素Temp拎出增补空缺
   Temp = H->Elements[H->Size--];
   // 4.遍历整个堆p*2<size,找到最末位结点的新位置
   for (Parent = 1; Parent * 2 < H->Size; Parent = Child) {
       Child = Parent * 2;
       // 5.比较左、右子树的大小，取较大者
       if (Child != H->Size && (H->Elements[Child] < H->Elements[Child + 1])) {
           Child++;
       }
       //6. 如果最末位元素Temp大于左、右子树，则不处理，否则左、右子树较大者覆盖父结点
       if (Temp > H->Elements[Child])
           break;
       else
           H->Elements[Parent] = H->Elements[Child];
   }
   // 7.遍历结束，找到Temp位置parent，插入元素
   H->Elements[Parent] = Temp;
   return MaxItem;
}

/**
* 下滤:将H->Elemets[p]为根的子堆调整为最大堆
* @param H
* @param P
*/
void PercDown(MaxHeap H, int P) {
   int Parent, Child;
   ElementType X;
   // 1.找到位置P对应的值X
   X = H->Elements[P];
   // 2.遍历以P为根结点的整棵树
   for (Parent = P; Parent * 2 <= H->Size; Parent = Child) {
       Child = Parent * 2;
       // 3.取结点左、右子树较大者
       if (Child != H->Size && (H->Elements[Child] < H->Elements[Child + 1]))
           Child++;
           // 4.如果父结点X的值比子结点大，不处理，否则父子换位
       if (X >= H->Elements[Child])
           break;
       else
           H->Elements[Parent] = H->Elements[Child];
   }
   // 5.遍历结束，找到P对应的位置Parent，插入原来的根结点值
   H->Elements[Parent] = X;
}

/**
* 建立最大堆，并不断地将小的元素下滤
* @param H
*/
void BuildHeap(MaxHeap H) {
   int i;
   // 1.从最后一个有子孩子的结点(size/2)向前进行下滤
   for (i = H->Size / 2; i > 0; i--) {
       PercDown(H, i);
   }
}

//验证构建、删除、插入大顶堆
int main() {
   int maxNum, i;
   ElementType value;
   printf("please input the heap numbers:\n");
   scanf("%d", &maxNum);
   MaxHeap Heap = Create(maxNum);
   printf("please input %d numbers:\n", maxNum);
   for (i = 0; i < maxNum; i++) {
       scanf("%d", &value);
       Insert(Heap, value);
   }
   printf("The root value is: %d\n", Heap->Elements[1]);
//    value = DeleteMax(Heap);
// 先注释插入时与根结点的比较,先只构造完全二叉树的结构，最通过下滤构造大顶堆
   BuildHeap(Heap);
   printf("after delete, the value is: %d\n", Heap->Elements[1]);
   return 0;
}