struct PriorityQueue{
int Cap;
int size;
int *data;
};
void Print(PriorityQueue* H)
{
for (int i = 0; i < H->size+1; i++)
{
printf("%d ", H->data[i]);
}
printf("\n");
}
PriorityQueue* CreateQueue(int MaxNum)
{
PriorityQueue *H;
H = (PriorityQueue*)malloc(sizeof(PriorityQueue));
if (H == NULL)
{
printf("Malloc failed!\n");
return NULL;
}
H->data = (int*)malloc(sizeof(int)*(MaxNum + 1));
H->Cap = MaxNum;
H->size = 0;
H->data[0] = -1;
return H;
}
void Insert(PriorityQueue* H, int val)
{
if (H->size + 1 > H->Cap)
{
printf("FULL!\n");
return;
}
int i = 0;
H->size++;
for (i = H->size; H->data[(int)(i / 2.0)] > val; i = (int)(i / 2.0))//令i在最外面的位置,val与i所在的根节点比较。如果根节点大于val,val需要上浮(但是先得让当前值下沉!)
{
H->data[i] = H->data[(int)(i / 2.0)];//下沉一个
}//循环结束后,i的位置就是找到的根节点
H->data[i] = val;
}
int DeleteMin(PriorityQueue* H)
{
int min = H->data[1];//去除第一个
int last = H->data[H->size--];//保存最后一个
int i = 1;
while (2 * i + 1 <= H->size)//循环结束标志
{
if (H->data[2 * i] >= H->data[2 * i + 1])
{
H->data[i] = H->data[2 * i + 1];
i = 2 * i + 1;
}
else
{
H->data[i] = H->data[2 * i];
i = 2 * i;
}
}
H->data[i] = last;
return min;
}
int main(int argc,char** argv)
{
PriorityQueue *H = CreateQueue(10);
Insert(H, 25);
Insert(H, 15);
Insert(H, 5);
Insert(H, 4);
Insert(H, 8);
Insert(H, 1);
Insert(H, 10);
Insert(H, 3);
Insert(H, 2);
Insert(H, 30);
Print(H);
DeleteMin(H);
Print(H);
return 0;
}