请在不使用STL的基础上,用c++实现一个标准优先队列ADT,包括push、pop、size、empty操作
时间: 2023-07-10 12:36:08 浏览: 101
好的,以下是一个不使用STL的C++实现:
```cpp
template <typename T>
class PriorityQueue {
public:
// 构造函数
PriorityQueue() {
// 初始化堆大小
capacity = 10;
// 初始化堆数组
heap = new T[capacity];
// 初始化堆大小为0
size = 0;
}
// 析构函数
~PriorityQueue() {
delete[] heap;
}
// 入队
void push(const T& value) {
// 如果堆已满,则进行扩容
if (size == capacity) {
resize();
}
// 将元素插入堆尾
heap[size++] = value;
// 上浮操作
siftUp(size - 1);
}
// 出队
void pop() {
// 如果堆为空,则直接返回
if (empty()) {
return;
}
// 将堆尾元素移到堆顶
heap[0] = heap[--size];
// 下沉操作
siftDown(0);
}
// 获取队列大小
int size() const {
return size;
}
// 判断队列是否为空
bool empty() const {
return size == 0;
}
// 获取队头元素
T top() const {
return heap[0];
}
private:
// 堆数组
T* heap;
// 堆的大小
int size;
// 堆的容量
int capacity;
// 上浮操作
void siftUp(int index) {
// 父节点的索引
int parent = (index - 1) / 2;
// 当前节点比父节点大,则交换它们
while (index > 0 && heap[index] > heap[parent]) {
std::swap(heap[index], heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
// 下沉操作
void siftDown(int index) {
while (true) {
// 左子节点的索引
int leftChild = index * 2 + 1;
// 右子节点的索引
int rightChild = index * 2 + 2;
// 用于比较的最大值索引
int maxIndex = index;
// 如果左子节点比当前节点大,则更新最大值索引
if (leftChild < size && heap[leftChild] > heap[maxIndex]) {
maxIndex = leftChild;
}
// 如果右子节点比当前节点大,则更新最大值索引
if (rightChild < size && heap[rightChild] > heap[maxIndex]) {
maxIndex = rightChild;
}
// 如果最大值索引不是当前节点,则交换它们,并继续下沉
if (maxIndex != index) {
std::swap(heap[index], heap[maxIndex]);
index = maxIndex;
}
else {
// 否则,已经满足堆的性质,退出循环
break;
}
}
}
// 扩容操作
void resize() {
// 新容量为原来的两倍
capacity *= 2;
// 新建一个更大的数组
T* newHeap = new T[capacity];
// 将原有元素复制到新数组中
for (int i = 0; i < size; i++) {
newHeap[i] = heap[i];
}
// 删除原有数组
delete[] heap;
// 更新指针
heap = newHeap;
}
};
```
使用方式与前面的示例相同。需要注意的是,这里实现了一个大根堆,因此需要比较运算符“>”来进行大小比较。如果需要实现小根堆,可以将比较运算符改为“<”。
阅读全文