1.堆

堆（Heap）是一种特殊的完全二叉树数据结构，具有以下两个主要特性：

• 结构特性：
  • 堆是一棵完全二叉树，即除了最后一层的叶子节点外，每一层都是满的，最后一层的叶子节点从左向右依次排列。
• 堆序性：
  • 大堆（Max-Heap）：对于每个节点，父节点的值大于或等于其子节点的值。大堆中，根节点的值是所有节点中最大的。
  • 小堆（Min-Heap）：对于每个节点，父节点的值小于或等于其子节点的值。小堆中，根节点的值是所有节点中最小的。

 2.堆的实现

 

2.1堆的定义

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;size_t size;size_t capacity;
}HP;

2.2堆初始化

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}

2.3堆的销毁

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

2.3打印

void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}

2.4向上调整堆的顺序（小堆）

向上调整，只是传入子节点下标，类似与向下调整算法。

void Swap(HPDataType* pa, HPDataType* pb)
{HPDataType tmp = *pa;*pa = *pb;*pb = tmp;
}void AdjustUp(HPDataType* a, size_t child)
{size_t parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])     //小堆//if (a[child] > a[parent])   //大堆{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.5向堆中插入数据

将数据插入到最后一个，然后利用向上调整算法

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);if (tmp == NULL){printf("realloc failed\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;++php->size;// 向上调整，控制保持是一个小堆AdjustUp(php->a, php->size - 1);
}

2.6向下调整堆的顺序（小堆）

void AdjustDown(HPDataType* a, size_t size, size_t root)
{size_t parent = root;size_t child = parent * 2 + 1;while (child < size){// 1、选出左右孩子中小的那个if (child + 1 < size && a[child+1] < a[child]){++child;}// 2、如果孩子小于父亲，则交换，并继续往下调整if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.7删除堆顶的数据。

// 删除堆顶的数据。
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}

2.8判断堆是否为空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

2.9查看堆的大小

size_t HeapSize(HP* php)
{assert(php);return php->size;
}

2.10返回堆顶数据

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}