发布时间:2023-12-27 11:00
using System;
using System.Collections.Generic;
namespace MyDS
{
class PriorityQueue
{
private int[] array;
public int Count { get; private set; }
private bool isMax;//true表示大顶堆,默认的,false表示小顶堆
public PriorityQueue(bool isMax=true)
{
//初始大小为16
array=new int[16];
this.isMax = isMax;
}
///
/// 入队
///
///
public void Enqueue(int key)
{
if (Count >= array.Length)
{
Resize();
}
array[Count++] = key;//将新元素放在队尾
UpAdjust();//队尾元素破坏了二叉堆,将队尾元素上浮
}
///
/// 队首元素出队
///
///
public int Dequeue()
{
if (Count <= 0)
{
throw new InvalidOperationException(\"优先队列为空\");
}
int head = array[0];
array[0] = array[--Count];//让最后一个元素移动到堆顶
DownAdjust();//队首元素破坏了二叉堆,将队首元素下沉
return head;
}
///
/// 获取队首元素
///
///
public int GetHead()
{
if (Count > 0)
return array[0];
else
{
throw new InvalidOperationException(\"优先队列为空\");
}
}
///
/// 队列是否为空
///
///
public bool IsEmpty()
{
return (Count == 0);
}
///
/// 清空队列
///
public void Clear()
{
Count = 0;
}
///
/// 判断队列是否包含某元素
///
///
///
public bool Contains(int key)
{
bool contains = false;
for (int i = 0; i < Count; i++)
{
if (array[i] == key)
{
contains = true;
break;
}
}
return contains;
}
///
/// 上浮
///
private void UpAdjust()
{
int childIndex = Count - 1;
int parentIndex = (childIndex - 1) >> 1;
int temp = array[childIndex];
while (parentIndex >= 0 && (isMax? (temp > array[parentIndex]): (temp < array[parentIndex])))
{
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (childIndex - 1) >> 1;
}
array[childIndex] = temp;
}
///
/// 下沉
///
private void DownAdjust()
{
int temp = array[0];
int index = 0;
for (int i = 1; i < Count; i = 2 * i + 1)
{
if (i + 1 < Count && (isMax?( array[i] < array[i + 1]): (array[i] > array[i + 1])))
{
i++;
}
if (isMax ? (temp < array[i]): (temp > array[i]))
{
array[index] = array[i];
index = i;
}
else
{
break;
}
}
array[index] = temp;
}
///
/// 扩容
///
private void Resize()
{
int[] newArray=new int[2*array.Length];
for (int i = 0; i < array.Length; i++)
{
newArray[i] = array[i];
}
array = newArray;
}
}
}