TransportationSystem/test_MinindexHeap.cpp at master · ChineseAegis/TransportationSystem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include "catch.hpp"
#include "MinIndexHeap.hpp"  // 包含你的 MinIndexHeap 头文件

TEST_CASE("MinIndexHeap functionality", "[MinIndexHeap]") {
    SECTION("Heapify an array") {
        int arr[] = { 5, 3, 8, 1, 2 };
        MinIndexHeap<int> heap(arr, 5);
        int min;
        REQUIRE(heap.removeMin(min));
        REQUIRE(min == 1);
    }

    SECTION("Insert elements") {
        MinIndexHeap<int> heap(3);
        REQUIRE(heap.Insert(5));
        REQUIRE(heap.Insert(3));
        REQUIRE(heap.Insert(8));
        // Testing auto-resize
        REQUIRE(heap.Insert(4));
        int min;
        REQUIRE(heap.removeMin(min));
        REQUIRE(min == 3);
    }

    SECTION("Remove min element") {
        MinIndexHeap<int> heap(10);
        REQUIRE(heap.Insert(5));
        REQUIRE(heap.Insert(3));
        int min;
        REQUIRE(heap.removeMin(min));
        REQUIRE(min == 3);
        REQUIRE(heap.removeMin(min));
        REQUIRE(min == 5);
    }

    SECTION("Modify element") {
        MinIndexHeap<int> heap(10);
        REQUIRE(heap.Insert(5));
        REQUIRE(heap.Insert(3));
        REQUIRE(heap.Modify(1, 1)); // 修改第二个元素的值为 1
        int min;
        REQUIRE(heap.removeMin(min));
        REQUIRE(min == 1);
    }

    SECTION("Handle auto-resize on capacity exceed") {
        MinIndexHeap<int> heap(2);
        REQUIRE(heap.Insert(5));
        REQUIRE(heap.Insert(3));
        REQUIRE(heap.Insert(10)); // 应该自动扩容
        REQUIRE(heap.Insert(1));
        int min;
        REQUIRE(heap.removeMin(min));
        REQUIRE(min == 1); // 确认自动扩容后元素正确
    }
    SECTION("1") {
        MinIndexHeap<int> heap; int mov;
        heap.Insert(0);
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.Insert(10);
        heap.Insert(20);
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.Insert(15);
        heap.Insert(15);
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.removeMin(mov);
        std::cout << mov << std::endl;
    }
    SECTION("2") {
        MinIndexHeap<int> heap; int mov;
        heap.Insert(0);
        heap.Insert(10000);
        heap.Insert(10000);
        heap.Insert(10000);
        heap.Insert(10000);
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.Insert(10);
        heap.Insert(20);
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.Insert(15);
        heap.Insert(15);
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.removeMin(mov);
        std::cout << mov << std::endl;
        heap.removeMin(mov);
        std::cout << mov << std::endl;
    }
}