搭建一个购物网站,校园二手市场网站开发,wordpress本地路径,企业信用信息查询公示报告目录
一、队列
二、树
三、堆 在现代计算机科学与工程领域#xff0c;队列、树和堆是三种极其重要的基础数据结构#xff0c;它们各自具有独特的特点和应用。在日常开发中#xff0c;合理选择和使用这些数据结构可以显著提高程序的效率和可维护性。它们不仅奠定了算法设计…目录
一、队列
二、树
三、堆 在现代计算机科学与工程领域队列、树和堆是三种极其重要的基础数据结构它们各自具有独特的特点和应用。在日常开发中合理选择和使用这些数据结构可以显著提高程序的效率和可维护性。它们不仅奠定了算法设计的理论基础还在系统开发、数据处理和实际应用中扮演着不可或缺的角色。
一、队列
队列Queue是一种特殊的线性数据结构它遵循先进先出First In First Out, FIFO的原则。这意味着最早进入队列的元素将是最先被移除的元素。在队列中插入操作通常发生在队尾rear而删除操作则发生在队头front。这种特性使得队列非常适合用来模拟现实生活中的排队现象如银行或超市收银台前的顾客排队。
1. 队列的定义与特点
定义队列是一种特殊的线性表只允许在一端称为队尾插入数据在另一端称为队头删除数据。
特点
先进先出队列中最早加入的元素最先被移除。
单向操作数据只能从队尾插入从队头移除。
受限性与栈类似操作位置有限不支持随机访问。
2. 队列的基本操作 入队Enqueue在队尾插入一个元素。 出队Dequeue从队头移除一个元素。 获取队头元素Front查看队头元素但不移除。 检查是否为空IsEmpty判断队列中是否还有数据。 检查是否已满IsFull对于静态实现的队列判断队列是否达到容量限制。
3. 队列的分类
3.1 普通队列
最简单的队列形式。
操作规则
入队在队尾插入数据。
出队从队头移除数据。
#include stdio.h
#include stdlib.h
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front; // 指向队头int rear; // 指向队尾
} Queue;// 初始化队列
void initQueue(Queue *q) {q-front 0;q-rear 0;
}// 判断队列是否为空
int isEmpty(Queue *q) {return q-front q-rear;
}// 判断队列是否已满
int isFull(Queue *q) {return q-rear MAX_SIZE;
}// 入队操作
void enqueue(Queue *q, int value) {if (isFull(q)) {printf(Queue is full\n);return;}q-data[q-rear] value;
}// 出队操作
int dequeue(Queue *q) {if (isEmpty(q)) {printf(Queue is empty\n);return -1;}return q-data[q-front];
}int main() {Queue q;initQueue(q);enqueue(q, 10);enqueue(q, 20);printf(Dequeued: %d\n, dequeue(q));printf(Dequeued: %d\n, dequeue(q));return 0;
}3.2 循环队列
为了解决普通队列中由于数据出队导致的空间浪费问题采用环状的存储方式。
特点通过逻辑上的首尾相连使队列能高效利用存储空间。
实现利用取模运算控制队列的首尾相连。
#include stdio.h
#include stdlib.h
#define MAX_SIZE 5typedef struct {int data[MAX_SIZE];int front; // 指向队头int rear; // 指向队尾
} CircularQueue;// 初始化循环队列
void initCircularQueue(CircularQueue *q) {q-front q-rear 0;
}// 判断循环队列是否为空
int isCircularQueueEmpty(CircularQueue *q) {return q-front q-rear;
}// 判断循环队列是否已满
int isCircularQueueFull(CircularQueue *q) {return (q-rear 1) % MAX_SIZE q-front;
}// 入队操作
void circularEnqueue(CircularQueue *q, int value) {if (isCircularQueueFull(q)) {printf(Circular Queue is full\n);return;}q-data[q-rear] value;q-rear (q-rear 1) % MAX_SIZE;
}// 出队操作
int circularDequeue(CircularQueue *q) {if (isCircularQueueEmpty(q)) {printf(Circular Queue is empty\n);return -1;}int value q-data[q-front];q-front (q-front 1) % MAX_SIZE;return value;
}int main() {CircularQueue q;initCircularQueue(q);circularEnqueue(q, 10);circularEnqueue(q, 20);printf(Dequeued: %d\n, circularDequeue(q));printf(Dequeued: %d\n, circularDequeue(q));return 0;
}3.3 双端队列Deque, Double-Ended Queue
支持在队列的两端进行入队和出队操作。
分类
输入受限双端队列只能从一端入队。
输出受限双端队列只能从一端出队。
#include stdio.h
#include stdlib.h
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front; // 指向队头int rear; // 指向队尾
} Deque;// 初始化双端队列
void initDeque(Deque *dq) {dq-front dq-rear 0;
}// 判断是否为空
int isDequeEmpty(Deque *dq) {return dq-front dq-rear;
}// 判断是否已满
int isDequeFull(Deque *dq) {return (dq-rear 1) % MAX_SIZE dq-front;
}// 从队头插入
void enqueueFront(Deque *dq, int value) {if (isDequeFull(dq)) {printf(Deque is full\n);return;}dq-front (dq-front - 1 MAX_SIZE) % MAX_SIZE;dq-data[dq-front] value;
}// 从队尾插入
void enqueueRear(Deque *dq, int value) {if (isDequeFull(dq)) {printf(Deque is full\n);return;}dq-data[dq-rear] value;dq-rear (dq-rear 1) % MAX_SIZE;
}// 从队头删除
int dequeueFront(Deque *dq) {if (isDequeEmpty(dq)) {printf(Deque is empty\n);return -1;}int value dq-data[dq-front];dq-front (dq-front 1) % MAX_SIZE;return value;
}// 从队尾删除
int dequeueRear(Deque *dq) {if (isDequeEmpty(dq)) {printf(Deque is empty\n);return -1;}dq-rear (dq-rear - 1 MAX_SIZE) % MAX_SIZE;return dq-data[dq-rear];
}int main() {Deque dq;initDeque(dq);enqueueRear(dq, 10);enqueueRear(dq, 20);enqueueFront(dq, 5);printf(Dequeued from front: %d\n, dequeueFront(dq));printf(Dequeued from rear: %d\n, dequeueRear(dq));return 0;
}3.4 优先队列Priority Queue
队列中的每个元素附加一个优先级根据优先级决定元素的出队顺序。
实现方式常用堆Heap结构实现。
#include stdio.h
#include stdlib.h
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int size; // 当前优先队列大小
} PriorityQueue;// 初始化优先队列
void initPriorityQueue(PriorityQueue *pq) {pq-size 0;
}// 插入元素到优先队列
void enqueuePriorityQueue(PriorityQueue *pq, int value) {if (pq-size MAX_SIZE) {printf(Priority Queue is full\n);return;}pq-data[pq-size] value;int i pq-size - 1;// 上浮操作while (i 0 pq-data[i] pq-data[(i - 1) / 2]) {int temp pq-data[i];pq-data[i] pq-data[(i - 1) / 2];pq-data[(i - 1) / 2] temp;i (i - 1) / 2;}
}// 移除优先队列中的最小元素
int dequeuePriorityQueue(PriorityQueue *pq) {if (pq-size 0) {printf(Priority Queue is empty\n);return -1;}int min pq-data[0];pq-data[0] pq-data[--pq-size];int i 0;// 下沉操作while (2 * i 1 pq-size) {int smallest 2 * i 1;if (smallest 1 pq-size pq-data[smallest 1] pq-data[smallest]) {smallest;}if (pq-data[i] pq-data[smallest]) break;int temp pq-data[i];pq-data[i] pq-data[smallest];pq-data[smallest] temp;i smallest;}return min;
}int main() {PriorityQueue pq;initPriorityQueue(pq);enqueuePriorityQueue(pq, 15);enqueuePriorityQueue(pq, 10);enqueuePriorityQueue(pq, 5);printf(Dequeued: %d\n, dequeuePriorityQueue(pq));printf(Dequeued: %d\n, dequeuePriorityQueue(pq));return 0;
}4. 队列的实现方式
4.1 顺序队列基于数组
优点实现简单。
缺点如果不使用循环队列出队会导致存储空间浪费。数组大小固定可能导致空间浪费或溢出。
#include stdio.h
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front;int rear;
} Queue;void initQueue(Queue *q) {q-front q-rear 0;
}int isEmpty(Queue *q) {return q-front q-rear;
}int isFull(Queue *q) {return (q-rear 1) % MAX_SIZE q-front;
}void enqueue(Queue *q, int value) {if (isFull(q)) {printf(Queue is full\n);return;}q-data[q-rear] value;q-rear (q-rear 1) % MAX_SIZE;
}int dequeue(Queue *q) {if (isEmpty(q)) {printf(Queue is empty\n);return -1;}int value q-data[q-front];q-front (q-front 1) % MAX_SIZE;return value;
}int main() {Queue q;initQueue(q);enqueue(q, 10);enqueue(q, 20);printf(Dequeued: %d\n, dequeue(q));printf(Dequeued: %d\n, dequeue(q));return 0;
}4.2 链式队列基于链表
优点动态分配存储空间无需提前固定大小。
缺点需要额外的指针开销。
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node *next;
} Node;typedef struct {Node *front;Node *rear;
} Queue;void initQueue(Queue *q) {q-front q-rear NULL;
}int isEmpty(Queue *q) {return q-front NULL;
}void enqueue(Queue *q, int value) {Node *newNode (Node *)malloc(sizeof(Node));newNode-data value;newNode-next NULL;if (q-rear) {q-rear-next newNode;} else {q-front newNode;}q-rear newNode;
}int dequeue(Queue *q) {if (isEmpty(q)) {printf(Queue is empty\n);return -1;}Node *temp q-front;int value temp-data;q-front temp-next;if (q-front NULL) {q-rear NULL;}free(temp);return value;
}int main() {Queue q;initQueue(q);enqueue(q, 10);enqueue(q, 20);printf(Dequeued: %d\n, dequeue(q));printf(Dequeued: %d\n, dequeue(q));return 0;
}4.3 循环队列
原理利用取模运算实现首尾相连。
操作公式
入队位置(rear1)%capacity
出队位置(front1)%capacity
优点充分利用存储空间。
缺点实现稍微复杂。
#include stdio.h
#include stdlib.h
#define MAX_SIZE 5typedef struct {int data[MAX_SIZE];int front; // 指向队头int rear; // 指向队尾
} CircularQueue;// 初始化循环队列
void initCircularQueue(CircularQueue *q) {q-front q-rear 0;
}// 判断循环队列是否为空
int isCircularQueueEmpty(CircularQueue *q) {return q-front q-rear;
}// 判断循环队列是否已满
int isCircularQueueFull(CircularQueue *q) {return (q-rear 1) % MAX_SIZE q-front;
}// 入队操作
void circularEnqueue(CircularQueue *q, int value) {if (isCircularQueueFull(q)) {printf(Circular Queue is full\n);return;}q-data[q-rear] value;q-rear (q-rear 1) % MAX_SIZE;
}// 出队操作
int circularDequeue(CircularQueue *q) {if (isCircularQueueEmpty(q)) {printf(Circular Queue is empty\n);return -1;}int value q-data[q-front];q-front (q-front 1) % MAX_SIZE;return value;
}int main() {CircularQueue q;initCircularQueue(q);circularEnqueue(q, 10);circularEnqueue(q, 20);printf(Dequeued: %d\n, circularDequeue(q));printf(Dequeued: %d\n, circularDequeue(q));return 0;
}5. 队列的典型应用场景 广度优先搜索BFS在图算法中使用队列存储当前层次的节点。 任务调度在操作系统中用队列管理任务执行顺序如打印任务、进程调度等。 数据缓冲在网络通信中队列用于暂存数据以待后续处理。 生产者-消费者模型队列作为中间缓冲区连接生产者与消费者。 消息队列在分布式系统中用于异步通信和任务分发。
6. 队列的优势与局限性
优势
简单易用先进先出的操作模式清晰且自然。
操作高效逻辑简单易于实现和使用。插入和删除操作的时间复杂度为 O(1)O(1)O(1)。
应用广泛从算法设计到工程实践队列都有重要作用。 局限性
操作受限只能在两端进行操作不支持随机访问。
空间利用问题普通队列在频繁出队时可能造成空间浪费。
普通队列效率低出队后空间不可复用。
7、小结
队列作为一种基础数据结构因其先进先出的特性在数据的有序处理、任务调度、广度搜索等场景中发挥了重要作用。 通过对队列的分类、操作及实现方式的深入理解开发者能够灵活运用队列解决各种复杂问题并优化程序性能。
顺序队列适用于固定大小的简单队列场景但会导致存储空间浪费。链式队列通过动态分配解决空间问题适合大小不确定的队列但需额外的内存指针。循环队列通逻辑上的首尾相连实现存储空间的高效利用是一种改进的顺序队列方式。
二、树
树是一种 非线性数据结构以分层的方式存储数据。它由一个根节点Root和多个子节点Child组成每个节点可能有多个子节点但只有一个父节点Parent。树特别适用于分层组织和快速查找的场景。
1. 树的定义与特点
定义
树是由节点和边组成的结构具有以下特点
树中只有一个根节点。除根节点外的每个节点有且仅有一个父节点。节点之间通过边连接形成一个无环的层次结构。
树的特点
递归定义树是一个根节点和若干子树的集合每棵子树本质上也是一棵树。
无环性从根节点到任意节点仅有一条路径。
层次结构树具有明显的分层结构数据之间存在父子关系。
节点关系父节点直接指向当前节点的节点。子节点被当前节点指向的节点。兄弟节点具有同一个父节点的节点。叶子节点没有子节点的节点。根节点没有父节点的节点。
2. 树的基本概念
根节点Root没有父节点的节点。
父节点Parent直接指向其他节点的节点。
子节点Child被某个节点直接指向的节点。
叶子节点Leaf没有子节点的节点。
度Degree节点的子节点个数称为该节点的度树的最大度称为树的度。
层次Level树中节点的层次从根节点开始根节点为第 1 层其子节点为第 2 层以此类推。
高度Height节点高度从当前节点到叶子节点的最长路径上的边数。树高度根节点的高度。
深度Depth节点的深度是从根节点到当前节点的路径长度。
路径Path从一个节点到另一个节点经过的所有节点和边。
森林Forest由多棵互不相交的树组成的集合。
3. 树的分类
按节点连接关系分类
普通树节点可以有任意数量的子节点。
// 树的节点定义
typedef struct TreeNode {int value;struct TreeNode **children; // 子节点指针数组int childCount; // 子节点数
} TreeNode;
二叉树每个节点最多有两个子节点分别是左子节点和右子节点。 特殊的二叉树
// 定义二叉树节点
typedef struct TreeNode {int value;struct TreeNode* left;struct TreeNode* right;
} TreeNode;
搜索二叉树BST左子树的所有节点小于根节点右子树的所有节点大于根节点。
// 插入
TreeNode* insertBST(TreeNode* root, int value) {if (!root) return createTreeNode(value);if (value root-value)root-left insertBST(root-left, value);else if (value root-value)root-right insertBST(root-right, value);return root;
}// 搜索
TreeNode* searchBST(TreeNode* root, int value) {if (!root || root-value value) return root;if (value root-value)return searchBST(root-left, value);return searchBST(root-right, value);
}平衡二叉树左右子树高度差不超过 1。满二叉树所有层的节点数都达到最大值。完全二叉树所有层均满最后一层的节点从左到右连续排列。多叉树每个节点可以有多个子节点例如 N 叉树。Trie 树一种特殊的多叉树用于快速存储和检索字符串。红黑树、AVL树自平衡二叉搜索树用于保证操作的效率。
#include stdio.h
#include stdlib.h// AVL 树节点定义
typedef struct AVLNode {int value;int height;struct AVLNode* left;struct AVLNode* right;
} AVLNode;// 获取节点高度
int getHeight(AVLNode* node) {return node ? node-height : 0;
}// 计算平衡因子
int getBalanceFactor(AVLNode* node) {return getHeight(node-left) - getHeight(node-right);
}// 创建新节点
AVLNode* createAVLNode(int value) {AVLNode* node (AVLNode*)malloc(sizeof(AVLNode));node-value value;node-height 1;node-left NULL;node-right NULL;return node;
}// 右旋
AVLNode* rightRotate(AVLNode* y) {AVLNode* x y-left;AVLNode* T x-right;x-right y;y-left T;y-height 1 (getHeight(y-left) getHeight(y-right) ? getHeight(y-left) : getHeight(y-right));x-height 1 (getHeight(x-left) getHeight(x-right) ? getHeight(x-left) : getHeight(x-right));return x;
}// 左旋
AVLNode* leftRotate(AVLNode* x) {AVLNode* y x-right;AVLNode* T y-left;y-left x;x-right T;x-height 1 (getHeight(x-left) getHeight(x-right) ? getHeight(x-left) : getHeight(x-right));y-height 1 (getHeight(y-left) getHeight(y-right) ? getHeight(y-left) : getHeight(y-right));return y;
}// 插入节点
AVLNode* insertAVL(AVLNode* root, int value) {if (!root) return createAVLNode(value);if (value root-value)root-left insertAVL(root-left, value);else if (value root-value)root-right insertAVL(root-right, value);elsereturn root;root-height 1 (getHeight(root-left) getHeight(root-right) ? getHeight(root-left) : getHeight(root-right));int balance getBalanceFactor(root);// 左左if (balance 1 value root-left-value)return rightRotate(root);// 右右if (balance -1 value root-right-value)return leftRotate(root);// 左右if (balance 1 value root-left-value) {root-left leftRotate(root-left);return rightRotate(root);}// 右左if (balance -1 value root-right-value) {root-right rightRotate(root-right);return leftRotate(root);}return root;
}3.2 按数据组织方式分类
堆Heap完全二叉树满足堆序性质。
并查集树用于解决连通性问题支持合并和查找操作。
4. 树的基本操作
遍历深度优先遍历DFS前序遍历根 → 左 → 右。中序遍历左 → 根 → 右。后序遍历左 → 右 → 根。广度优先遍历BFS层次遍历按层次从上到下从左到右依次访问节点。
插入根据树的性质插入节点例如在二叉搜索树中插入时需保持排序规则。
删除移除指定节点后需调整树结构以保持性质例如删除二叉搜索树节点时需替换为合适的继承节点。
查找按树的规则查找特定节点如二叉搜索树的查找效率为 O(logn)O(\log n)O(logn)。
高度计算递归或迭代计算节点的高度。
5. 树的存储方式
链式存储
每个节点通过指针指向其子节点和父节点。常见于动态树结构如链表表示的二叉树。
typedef struct TreeNode {int value;struct TreeNode *left;struct TreeNode *right;
} TreeNode;顺序存储使用数组存储完全二叉树。左子节点的索引为 2i1右子节点的索引为 2i2。
#include stdio.h
#include stdlib.h#define MAX_SIZE 100 // 最大节点数typedef struct CompleteBinaryTree {int data[MAX_SIZE]; // 数组存储完全二叉树的节点值int size; // 当前节点数
} CompleteBinaryTree;// 初始化完全二叉树
void initTree(CompleteBinaryTree* tree) {tree-size 0;
}// 插入节点
void insertNode(CompleteBinaryTree* tree, int value) {if (tree-size MAX_SIZE) {printf(Tree is full. Cannot insert more nodes.\n);return;}tree-data[tree-size] value;tree-size;
}// 获取左子节点索引
int getLeftChildIndex(int index) {return 2 * index 1;
}// 获取右子节点索引
int getRightChildIndex(int index) {return 2 * index 2;
}// 打印树的层序遍历
void printTree(CompleteBinaryTree* tree) {printf(Tree: );for (int i 0; i tree-size; i) {printf(%d , tree-data[i]);}printf(\n);
}// 打印节点的左右子节点
void printChildren(CompleteBinaryTree* tree, int index) {if (index tree-size) {printf(Invalid index\n);return;}printf(Node %d: , tree-data[index]);int leftIndex getLeftChildIndex(index);int rightIndex getRightChildIndex(index);if (leftIndex tree-size)printf(Left Child %d , tree-data[leftIndex]);elseprintf(Left Child NULL );if (rightIndex tree-size)printf(Right Child %d , tree-data[rightIndex]);elseprintf(Right Child NULL );printf(\n);
}int main() {CompleteBinaryTree tree;initTree(tree);// 插入节点insertNode(tree, 1);insertNode(tree, 2);insertNode(tree, 3);insertNode(tree, 4);insertNode(tree, 5);insertNode(tree, 6);// 打印树printTree(tree);// 打印某些节点的子节点printChildren(tree, 0); // 根节点printChildren(tree, 1); // 第二层左节点printChildren(tree, 2); // 第二层右节点return 0;
}6. 树的应用场景
二叉树二叉搜索树BST高效查找、插入、删除。堆优先队列的实现。Trie 树快速字符串匹配、前缀查询。红黑树、AVL 树数据库索引、动态集合操作。决策树机器学习中的分类和回归算法。表达式树表达式求值。文件系统文件和目录的层次管理。
7. 树的优势与局限性
优势
自然表示分层结构适合数据的分级存储。支持高效的查找、插入和删除操作。可扩展性强灵活适应不同场景。
局限性
链式存储需要额外的指针开销。树结构的实现较为复杂维护特性如平衡需付出额外代价。不适合随机访问性能劣于数组。
8. 小结
树作为一种基础数据结构在理论研究和实际工程中都具有重要地位广泛应用于文件系统、数据库索引、路由表等场景。通过不同种类的树如二叉树、AVL树、红黑树等我们可以根据需求选择适合的结构来优化数据操作效率。掌握树的基本知识和实现方法是深入学习算法与数据结构的重要一步。
二叉树及其变种解决高效数据存储与操作问题。Trie 树适合字符串处理场景。红黑树、AVL 树优化动态数据的平衡性。掌握树的基本原理、特性及其适用场景是深入理解算法与系统设计的关键。
三、堆
1、堆的定义与特性
堆Heap是一种特殊的基于树的抽象数据类型特殊的完全二叉树堆通常用于实现优先队列在这种结构中最高优先级的元素总是位于根节点。 堆满足以下特性对于任意给定的节点i如果P是i的父节点那么P的键值或元素要么大于等于最大堆, max-heap要么小于等于最小堆, min-heapi的键值。
大顶堆Max Heap任意节点的值都不小于其子节点的值堆顶为最大值。小顶堆Min Heap任意节点的值都不大于其子节点的值堆顶为最小值。
完全二叉树 (Complete Binary Tree): 堆通常以完全二叉树的形式实现这意味着除了最底层外所有层都是满的并且最底层的节点尽可能靠左排列。
存储结构通常使用数组来存储堆逻辑上的父子节点关系可以通过索引计算 父节点索引i 左子节点索引2i 1 右子节点索引2i 2 若需要访问父节点(i - 1) / 2
2、堆的基本操作 插入Insert在堆尾添加新元素。将新元素“上浮”Bubble Up以保持堆的性质。 删除堆顶元素Remove Top/Pop将堆顶元素替换为最后一个元素。删除最后一个元素。将新堆顶“下沉”Bubble Down以保持堆的性质。 堆化Heapify将无序数组调整为堆结构。从最后一个非叶节点开始对每个节点执行下沉操作。 堆排序Heap Sort利用堆性质进行排序。大顶堆适用于升序排序小顶堆适用于降序排序。 获取最大/最小元素 (Get-Max/Get-Min): 对于最大堆或最小堆根节点就是具有最大或最小键值的元素。
3、应用场景
优先队列 (Priority Queue): 堆是最常用的优先队列实现方式之一。在优先队列中每次取出的都是具有最高优先级的元素。
堆排序 (HeapSort): 一种高效的排序算法时间复杂度为O(n log n)。
选择问题 (Selection Problem): 如寻找数组中的第k大或第k小元素。
图算法: 例如Dijkstra算法和Prim算法其中需要频繁访问或更新最小权重的边。
内存管理: 某些操作系统使用堆来管理动态内存分配。
4、代码实现
1. 最大堆大顶堆
#include stdio.h
#include stdlib.h#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int size;
} MaxHeap;// 初始化堆
void initHeap(MaxHeap* heap) {heap-size 0;
}// 上浮操作
void bubbleUp(MaxHeap* heap, int index) {while (index 0) {int parent (index - 1) / 2;if (heap-data[index] heap-data[parent]) {// 交换int temp heap-data[index];heap-data[index] heap-data[parent];heap-data[parent] temp;index parent;} else {break;}}
}// 插入元素
void insert(MaxHeap* heap, int value) {if (heap-size MAX_SIZE) {printf(Heap is full!\n);return;}heap-data[heap-size] value;bubbleUp(heap, heap-size);heap-size;
}// 下沉操作
void bubbleDown(MaxHeap* heap, int index) {while (index * 2 1 heap-size) {int leftChild index * 2 1;int rightChild index * 2 2;int largerChild leftChild;if (rightChild heap-size heap-data[rightChild] heap-data[leftChild]) {largerChild rightChild;}if (heap-data[index] heap-data[largerChild]) {// 交换int temp heap-data[index];heap-data[index] heap-data[largerChild];heap-data[largerChild] temp;index largerChild;} else {break;}}
}// 删除堆顶元素
int removeTop(MaxHeap* heap) {if (heap-size 0) {printf(Heap is empty!\n);return -1;}int top heap-data[0];heap-data[0] heap-data[--heap-size];bubbleDown(heap, 0);return top;
}// 打印堆
void printHeap(MaxHeap* heap) {for (int i 0; i heap-size; i) {printf(%d , heap-data[i]);}printf(\n);
}int main() {MaxHeap heap;initHeap(heap);insert(heap, 10);insert(heap, 20);insert(heap, 15);insert(heap, 30);insert(heap, 25);printf(Heap elements: );printHeap(heap);printf(Removed top: %d\n, removeTop(heap));printf(Heap after removal: );printHeap(heap);return 0;
}2. 堆排序
void heapSort(int arr[], int n) {// 构建大顶堆for (int i n / 2 - 1; i 0; i--) {bubbleDown(arr, n, i);}// 逐步将堆顶移到数组末尾缩小堆的范围for (int i n - 1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;bubbleDown(arr, i, 0); // 对新的堆顶进行下沉}
}5、小结
堆是一种功能强大的数据结构适用于优先级处理和高效排序。它利用了完全二叉树的特性结合数组实现简化了存储和计算同时保持了良好的时间复杂度是许多算法和系统开发中的核心工具。 总结来说队列、树和堆都是非常重要的基础数据结构各自在不同的场景中发挥着不可替代的作用。队列适合处理按顺序排队的任务树则为数据的组织和快速检索提供了有效的解决方案而堆则常用于需要优先级排序的场合。通过深入理解它们的实现与应用开发者可以根据实际需求选择最适合的结构提高程序的性能与可靠性。掌握这些数据结构不仅能提升代码的效率还能为进一步学习复杂算法打下坚实的基础。
