C++ 实现小顶堆并判断命题真伪

"首先，我们需要实现一个小顶堆的类。可以使用数组来表示堆，数组的第一个元素为根结点，第i个元素的左孩子为2i，右孩子为2i+1。然后，我们可以依次插入给定的数字到堆中，插入完成后，我们可以根据给定的命题进行判断。\n\n下面是完整的C++代码实现：\n\ncpp\n#include <iostream>\nusing namespace std;\n\nclass MinHeap {\nprivate:\n int* heap;\n int capacity;\n int size;\n\npublic:\n MinHeap(int capacity) {\n this->capacity = capacity;\n this->size = 0;\n this->heap = new int[capacity + 1];\n }\n\n ~MinHeap() {\n delete[] heap;\n }\n\n void insert(int num) {\n if (size == capacity) {\n return;\n }\n\n size++;\n int i = size;\n while (i > 1 && num < heap[i/2]) {\n heap[i] = heap[i/2];\n i /= 2;\n }\n heap[i] = num;\n }\n\n bool isRoot(int num) {\n return heap[1] == num;\n }\n\n bool areSiblings(int num1, int num2) {\n int index1 = -1, index2 = -1;\n for (int i = 1; i <= size; i++) {\n if (heap[i] == num1) {\n index1 = i;\n }\n if (heap[i] == num2) {\n index2 = i;\n }\n }\n if (index1 == -1 || index2 == -1 || index1 == index2) {\n return false;\n }\n return index1/2 == index2/2;\n }\n\n bool isParent(int parent, int child) {\n int parentIndex = -1, childIndex = -1;\n for (int i = 1; i <= size; i++) {\n if (heap[i] == parent) {\n parentIndex = i;\n }\n if (heap[i] == child) {\n childIndex = i;\n }\n }\n if (parentIndex == -1 || childIndex == -1) {\n return false;\n }\n return parentIndex == childIndex/2;\n }\n\n bool isChild(int child, int parent) {\n int childIndex = -1, parentIndex = -1;\n for (int i = 1; i <= size; i++) {\n if (heap[i] == child) {\n childIndex = i;\n }\n if (heap[i] == parent) {\n parentIndex = i;\n }\n }\n if (childIndex == -1 || parentIndex == -1) {\n return false;\n }\n return childIndex/2 == parentIndex;\n }\n};\n\nint main() {\n int N, M;\n cin >> N >> M;\n\n MinHeap heap(N);\n for (int i = 0; i < N; i++) {\n int num;\n cin >> num;\n heap.insert(num);\n }\n\n for (int i = 0; i < M; i++) {\n string proposition;\n cin >> proposition;\n\n if (proposition == "is") {\n string type, relation;\n int num1, num2;\n cin >> num1 >> type >> relation >> num2;\n\n if (type == "root") {\n if (relation == "the") {\n cout << (heap.isRoot(num1) ? "T" : "F") << endl;\n }\n } else if (type == "and") {\n string relation2;\n int num3;\n cin >> relation2 >> num3;\n\n if (relation == "are" && relation2 == "siblings") {\n cout << (heap.areSiblings(num1, num2) ? "T" : "F") << endl;\n }\n } else if (type == "is") {\n string relation2;\n int num3;\n cin >> relation2 >> num3;\n\n if (relation == "the" && relation2 == "parent" && num3 == "of") {\n cout << (heap.isParent(num1, num2) ? "T" : "F") << endl;\n } else if (relation == "a" && relation2 == "child" && num3 == "of") {\n cout << (heap.isChild(num1, num2) ? "T" : "F") << endl;\n }\n }\n }\n }\n\n return 0;\n}\n\n\n这个程序首先读取插入元素的个数N和命题数M，然后依次读取N个要被插入堆的整数，并插入到堆中。最后，根据给定的命题进行判断，并输出结果。\n