背景
深入理解优先级队列的相关Push/Pop/构造优先级队列的相关操作。
代码
#include <cstdio>
#include <vector>
//#include <cint>
void Dump(const std::vector<int> & array) {
printf("size of array: %d\t", array.size());
for (int i = 0; i < array.size(); i++) {
printf("array[%d] = %d\n", i, array[i]);
}
}
// little heap: array[0] = MIN_INT;
int Push(std::vector<int> & array, int val) {
int sz = array.size();
if (sz == 1) {
//array[sz] = val;
array.insert(array.end(), val);
return 0;
}
// sz += 1;
array.insert(array.end(), val);
while (array[sz / 2] > val && sz >= 2) {
array[sz] = array[sz / 2];
//printf("array[%d] <--- array[%d]\n", sz, sz / 2);
sz = sz / 2;
}
array[sz] = val;
//printf("array[%d] = %d\n", sz, val);
Dump(array);
return 0;
}
int Pop(std::vector<int> & array) {
int return_val = array[1];
int sz = array.size();
int end_val = array[sz - 1];
if (sz == 1) {
return -1;
}
if (sz == 2 || sz == 3) {
array.erase(array.begin() + 1);
return return_val;
}
int index = 1;
while (index <= (sz - 1) / 2 && array[index] < end_val) {
if (array[2 * index] < array[2 * index + 1]) {
array[index] = array[2 * index];
printf("array[%d] <--- array[%d]\n", index, 2 * index);
index = 2 * index;
} else {
array[index] = array[2 * index + 1];
printf("array[%d] <--- array[%d]\n", index, 2 * index + 1);
index = 2 * index + 1;
}
}
array[index] = end_val;
array.erase(array.end());
Dump(array);
return return_val;
}
int main()
{
// printf("End....\n");
#if 1
//const char arr[10]{2,4,6,8};
std::vector<int> array;
//array[0] = -100000000; //std::min();
array.insert(array.end(), -1000000);
// printf("size of array is %d\n", array.size());
Push(array, 10);
Push(array, 5);
Push(array, 20);
Push(array, 6);
Push(array, 1);
Push(array, 60);
int osz = array.size();
for (int i = 0; i < osz - 1; i++) {
//for (int i = 0; i < array.size() - 1; i++) {
printf("i= %d now min value of array : %d\n", i, Pop(array));
}
#endif
return 0;
}