堆：關(guān)鍵碼的集合。

小堆（大堆）：任一結(jié)點(diǎn)的關(guān)鍵碼均小于等于（大于等于）它的的左右孩子的關(guān)鍵碼，位于堆頂結(jié)點(diǎn)的關(guān)鍵碼最?。ㄗ畲螅?，從根結(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的路徑上數(shù)組元素組成的序列都是遞增（遞減）的。

最小堆 & 最大堆.png

堆存儲(chǔ)在下標(biāo)為0的數(shù)組中。
已知 child :::::: 得parent=（child-1）/2
已知 parent :::::: 得 left=2parent+1
:::::: ::::: ::::::: :::::::::right=2parent+2

向下調(diào)整的應(yīng)用

• 堆的創(chuàng)建
• 堆的刪除（只能刪除堆頂元素，最后一個(gè)元素替代堆頂元素，向下調(diào)整以滿足堆的性質(zhì)）

向上調(diào)整的應(yīng)用

• 堆的插入 （只能在堆最后插入，插入之后，當(dāng)堆中的元素不再滿足堆的性質(zhì)時(shí)，就需要對(duì)堆進(jìn)行向上調(diào)整）

Heap.h

#define _CRT_SECURE_N0_WARNINGS 1

#include <stdio.h>
#include <assert.h>

typedef struct Heap{
    int array[100];
    int size;
}Heap;

static void Swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

//初始化
void HeapInit(Heap *pH, int source[], int size)
{
    for (int i = 0; i < size; i++)
    {
        pH->array[i] = source[i];
    }
    //更改堆的實(shí)際大小
    pH->size = size;
}

//向下調(diào)整 大堆
//root 指的是下標(biāo)
void HeapAdjustDown(Heap* pH, int root)
{
    int parent = root;
    
    while (1)
    {
        // 先判斷有沒有孩子（葉子結(jié)點(diǎn)）
        // 數(shù)組角度去想   -> 孩子的下標(biāo)是否越界
        // 只要判斷左孩子的下標(biāo)（因?yàn)槭峭耆鏄?
        int left = parent * 2 + 1;
        int right = parent * 2 + 2;

        if (pH->size < left) //越界 左孩子不存在
            return;

        int MaxChild = left;
        if ((pH->size >= right) && (pH->array[right]>pH->array[MaxChild]))
            MaxChild = right;

        if (pH->array[MaxChild] < pH->array[parent])
            return;

        //交換 
        int temp = pH->array[MaxChild];
        pH->array[MaxChild] = pH->array[parent];
        pH->array[parent] = temp;

        parent = MaxChild;
    }
}

//向上調(diào)整 大堆

void HeapAdjustUp(Heap* pH, int child)
{
    int parent;
    while (child > 0)
    {
        parent = (child - 1) / 2;
        if (pH->array[parent] >= pH->array[child])
            return;

        Swap(pH->array + parent, pH->array + child);

        child = parent;
    }
}

void HeapMakeHeap(Heap* pH)
{
    //最后一個(gè)非葉子結(jié)點(diǎn) last=size-1;
    //parent=(last-1)/2 = size/2-1;
    //所有非葉子結(jié)點(diǎn)的下標(biāo)為[0 ,size/2-1]
    //從物理結(jié)構(gòu)上來看 從后往前建堆 [最后一個(gè)非葉子結(jié)點(diǎn)size/2-1,0]
    for (int i = (pH->size - 2) / 2; i >= 0; i--) {
        HeapAdjustDown(pH, i);
    }
}

void HeapPop(Heap* pH)
{
    pH->array[0] = pH->array[pH->size - 1];
    pH->size = pH->size - 1;

    HeapAdjustDown(pH, 0);
}

int HeapTop(Heap* pH)
{
    return pH->array[0];
}

void HeapPush(Heap* pH,int data)
{
    assert(pH->size < 100);
    pH->array[pH->size++] = data;

    HeapAdjustUp(pH, pH->size-1);
}



void Test()
{
    int array[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
    int size = sizeof(array) / sizeof(int);

    Heap    heap;
    HeapInit(&heap, array, size);
    HeapMakeHeap(&heap);

    HeapPop(&heap);

    HeapPush(&heap, 100);
    printf("%d\n", HeapTop(&heap));

    printf("建堆完成\n");
}

Main.c

#define _CRT_SECURE_N0_WARNINGS 1

#include "Heap.h"

int main()
{
    //Test(); 
    return 0;
}