堆和优先队列
本帖最后由 pyzyd 于 2025-10-11 15:56 编辑堆有最大堆和最小堆，
堆是完全二叉树，
要求：
1.每个父节点大于（或小于）等于其子节点，左右子节点没有大小要求
2.堆最多只能有一个单个的左子节点，不能有多个结点，不能是单个的右子节点
90
/\
70 80
/ \ / \
6020 75 50
这就是一个最大堆
错误示例
1
/ \
2 3
/ /
堆的代码实现
/*
堆是特殊的树，
堆是完全二叉树，
堆中每一个节点的值都大于或等于其左右孩子节点的值，称为大顶堆（最大堆）；
堆中每一个节点的值都小于或等于其左右孩子节点的值，称为小顶堆（最小堆）。
堆可以用数组表示，数组中第i个元素，其左孩子为2i+1，右孩子为2i+2。
*/
#include <cstring>
#include <iomanip>
#include <iostream>
#include <string>
#include <cmath>
#define DEFAULT_CAPCITY 128
typedef int DataType;
typedef struct _Heap {
DataType *data;
int size;
int capacity;
} Heap;
bool initHeap(Heap &heap, int *original, int size);
bool insert(Heap &heap, DataType value);
static void buildHeap(Heap &heap);
static void adjustDown(Heap &heap, int index);
static void adjustUp(Heap &heap, int index);
int main() {
Heap hp;
int origVals[] = {1, 2, 3, 87, 93, 82, 92, 86, 95};
if (!initHeap(hp, origVals, sizeof(origVals) / sizeof(origVals))) {
std::cerr << "init heap failed!" << std::endl;
return -1;
}
if (typeid(1.0) == typeid(float)) {
std::cout << "1.0 is float" << std::endl;
} else {
std::cout << "1.0 is double" << std::endl;
}
insert(hp, 100);
return 0;
}
bool initHeap(Heap &heap, int *original, int size) {
if (original == nullptr || size <= 0) {
return false;
}
heap.capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;
heap.data = new DataType;
if (!heap.data) {
return false;
}
memcpy(heap.data, original, size * sizeof(int));
heap.size = size;
buildHeap(heap);
return true;
}
bool insert(Heap &heap, DataType value) {
if (heap.size == heap.capacity) {
return false;
}
int index = heap.size++;
heap.data = value;
adjustUp(heap, index);
return true;
}
/*
从最后一个非叶子结点（父节点 size / 2 - 1
的位置）逐个往前调整所有父节点（直到根节点），
确保每一个父节点都是一个最大堆，最终整个堆就是一个最大堆。
*/
static void buildHeap(Heap &heap) {
int i;
for (i = heap.size / 2 - 1; i >= 0; i--) {
adjustDown(heap, i);
}
}
/*
将当前节点和子节点调整成最大堆
*/
static void adjustDown(Heap &heap, int index) {
int cur = heap.data;
int parent, child;
for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
child = parent * 2 + 1;
// 比较左子节点和右子节点，取较大的那个
if ((child + 1) < heap.size &&
heap.data < heap.data) {
child++;
}
// 如果当前节点大于等于最大子节点，则不需要调整
if (cur >= heap.data) {
break;
} else {
// 否则，将当前节点和最大子节点交换
heap.data = heap.data;
heap.data = cur;
}
}
}
static void adjustUp(Heap &heap, int index) {
if (index < 0 || index >= heap.size) {
return;
}
while (index > 0) {
int parent = (index - 1) / 2;
if (heap.data <= heap.data) {
break;
}
// 交换当前节点与父节点
int temp = heap.data;
heap.data = heap.data;
heap.data = temp;
index = parent;
}
}
用堆来实现优先队列，利用了堆可以用数组存储的特性
#include <iostream>
#include <cstring>
#include <random>
#define DEFAULT_CAPACITY 128
typedef struct _task{
int priority;
}Task;
typedef Task DataType;
typedef struct _PriorityQueue {
DataType* data;
int size;
int capacity;
}PriorityQueue;
bool init(PriorityQueue &pq, DataType *original, int size);
bool push(PriorityQueue &pq, DataType value);
bool pop(PriorityQueue &pq, DataType &value);
bool isEmpty(PriorityQueue &pq);
bool isFull(PriorityQueue &pq);
void destroy(PriorityQueue &pq);
static void build(PriorityQueue &pq);
static void adjustDown(PriorityQueue &pq, int index);
static void adjustUp(PriorityQueue &pq, int index);
bool init(PriorityQueue &pq, DataType *original, int size) {
if (!original || size <= 0) {
return false;
}
pq.capacity = size > DEFAULT_CAPACITY ? size : DEFAULT_CAPACITY;
pq.data = new DataType;
// // 第一种初始化方式
// memcpy(pq.data, original, size * sizeof(DataType));
// pq.size = size;
// build(pq);
// 第二种初始化方式
pq.size = 0;
for (int i = 0; i < size; i++) {
push(pq, original);
}
return true;
}
static void build(PriorityQueue &pq) {
for (int i = pq.size / 2 - 1; i >= 0; i--) {
adjustDown(pq, i);
}
}
static void adjustDown(PriorityQueue &pq, int index) {
DataType cur = pq.data;
int parent = index;
int child;
//从当前的节点开始，向下调整子节点及子节点的子节点使数组满足堆的特性
while (parent * 2 + 1 < pq.size) {
child = parent * 2 + 1;
if (child + 1 < pq.size && pq.data.priority < pq.data.priority) {
child++;
}
if (pq.data.priority > cur.priority) {
pq.data = pq.data;// 子节点上移
parent = child;
} else {
break;
}
}
pq.data = cur;
}
bool push(PriorityQueue &pq, DataType value) {
if (isFull(pq)) {
return false;
}
pq.data = value;
adjustUp(pq, pq.size - 1);
return true;
}
bool isFull(PriorityQueue &pq) {
return pq.size == pq.capacity;
}
bool isEmpty(PriorityQueue &pq) {
return pq.size == 0;
}
static void adjustUp(PriorityQueue &pq, int index) {
DataType cur = pq.data;
int child, parent;
for (child = index; child > 0; child = parent) {
parent = (child - 1) / 2;
if (pq.data.priority < cur.priority) {
pq.data = pq.data;
pq.data = cur;
} else {
break;
}
}
}
bool pop(PriorityQueue &pq, DataType &value) {
if (isEmpty(pq)) {
return false;
}
value = pq.data;
pq.data = pq.data[--pq.size];
adjustDown(pq, 0);
return true;
}
void destroy(PriorityQueue &pq) {
delete[] pq.data;
pq.data = nullptr;
pq.size = pq.capacity = 0;
}
int main()
{
std::mt19937 gen(time(0)); // random device
std::uniform_int_distribution<int> dis(0, 9);
PriorityQueue pq;
Task tasks;
for (int i = 0; i < 7; i++) {
tasks.priority = dis(gen);
}
if (!init(pq, tasks, sizeof(tasks) / sizeof(Task))) {
std::cerr << "init failed" << std::endl;
return -1;
}
std::cout << "Tasks priority:" <<std::endl;
for (int i = 0; i < pq.size; i++){
std::cout << tasks.priority << " ";
}
std::cout << std::endl;
std::cout << "Priority queue:" << std::endl;
for (int i = 0; i < pq.size; i++){
std::cout << pq.data.priority << " ";
}
std::cout << std::endl;
push(pq, (Task){100});
std::cout << "Priority queue after push:" << std::endl;
for (int i = 0; i < pq.size; i++){
std::cout << pq.data.priority << " ";
}
std::cout << std::endl;
return 0;
}
/*堆排序——优化的选择排序*/
#include <iostream>
void heapify(int arr[], int n, int i) {
/*构建堆*/
int parent = i, child;
while ((child = 2 * parent + 1) < n) {
if (child + 1 < n && arr < arr) child++;
if (child < n && arr < arr) {
std::swap(arr, arr);
}else{
break;
}
parent = child;
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);// 从最后一个非叶子节点开始调整堆
for (int i = n - 1; i > 0; i--) {
std::swap(arr, arr);
heapify(arr, i, 0); // 调整前i个元素为最大堆，第i个之后的元素为已排序的元素
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr);
heapSort(arr, n);
std::cout << "Sorted array is \n";
for (int i = 0; i < n; i++) {
std::cout << arr << " ";
}
}
页:
[1]