背景

深入理解优先级队列的相关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;
}