04-树9. Path in a Heap

Posted on   |   In   |  

Insert a sequence of given numbers into an initially empty min-heap H. Then for any given index i, you are supposed to print the path from H[i] to the root.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (<=1000) which are the size of the input sequence, and the number of indices to be checked, respectively. Given in the next line are the N integers in [-10000, 10000] which are supposed to be inserted into an initially empty min-heap. Finally in the last line, M indices are given.

Output Specification:

For each index i in the input, print in one line the numbers visited along the path from H[i] to the root of the heap. The numbers are separated by a space, and there must be no extra space at the end of the line.

1
2
3
4
5
6
7
8
Sample Input:
5 3
46 23 26 24 10
5 4 3
Sample Output:
24 23 10
46 23 10
26 10

代码如下：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<iostream>
#include<vector>
using namespace std;

const int MAX_SIZE = 1001;
const int MIN_DATA = -100001;    //set sentinel
struct Heap
{
    int *heapArray;     //create dynamic array to storage element of heap
    int size;           //the size of current heap
    int capacity;       //the max size of heap

};

class MinHeap
{
public:
    MinHeap();
    ~MinHeap(){}
    Heap *CreateMinHeap(int maxSize);
    bool IsFull();
    bool IsEmpty();
    void InsertValMinHeap(int val,Heap *&MH);
    void Insert(int val);
    int DeleteMaxValMinHeap(Heap *&MH);
    int Delete();
    int FindVal(int position, vector<int> &ans);
private:
    Heap *m_h;
};
MinHeap::MinHeap()
{
    m_h = CreateMinHeap(MAX_SIZE);
}

Heap *MinHeap::CreateMinHeap(int maxSize)
{
    Heap *tempH = new Heap;
    tempH->heapArray = new int [maxSize];
    tempH->size = 0;
    tempH->capacity = maxSize;
    tempH->heapArray[0] = MIN_DATA;
    return tempH;
}

bool MinHeap::IsFull()
{
    if(m_h->size == m_h->capacity - 1)
    {
        return true;
    }
    return false;
}

bool MinHeap::IsEmpty()
{
    if(m_h->size == 0)
    {
        return true;
    }
    return false;
}

void MinHeap::Insert(int val)
{
    InsertValMinHeap(val, m_h);
}

void MinHeap::InsertValMinHeap(int val, Heap *&MH)
{
    if(IsFull())
    {
        cout << "heap is full " << endl;
        return;
    }
    int i = ++MH->size;
    for(; val < MH->heapArray[i/2]; i /= 2)
    {
        MH->heapArray[i] = MH->heapArray[i/2];
    }
    MH->heapArray[i] = val;
}

int MinHeap::DeleteMaxValMinHeap(Heap *&MH)
{
    if(IsEmpty())
    {
        cout << "heap is empty " << endl;
        return -1;
    }
    int maxData = MH->heapArray[1];
    int tempVal = MH->heapArray[MH->size--];
    int parent = 1, child = 0;
    for(; parent * 2 <= MH->size; parent = child)
    {
        child = parent * 2;
        if((child != MH->size) && (MH->heapArray[child + 1] < MH->heapArray[child]))
        {
            ++child;
        }
        if(tempVal <= MH->heapArray[child])
        {
            break;
        }
        MH->heapArray[parent] = MH->heapArray[child];
    }
    MH->heapArray[parent] = tempVal;
    return maxData;
}

int MinHeap::Delete()
{
   return DeleteMaxValMinHeap(m_h);
}
int MinHeap::FindVal(int position, vector<int> &ans)
{
    if(position < 0 || position > m_h->size)
    {
        cout << "can't find element " << endl;
    }
    else
    {
        for(int i = position; i > 0; i /= 2)
        {
            ans.push_back(m_h->heapArray[i]);
        }
    }
}

int main()
{
    int M = 0, N = 0;
    cin >> M >> N;
 //   vector<int> seqValVec;
    MinHeap mh;
    for(int i = 0; i < M; ++i)
    {
        int val = 0;
        cin >> val;
 //       seqValVec.push_back(val);
        mh.Insert(val);

    }
    mh.Delete();
    for(int i = 0; i < N; ++i)
    {
        int index = 0;
        cin >> index;
        vector<int> ans;
        mh.FindVal(index,ans);
        for(int i = 0; i < ans.size(); ++i)
        {
            cout << ans[i] << (i == ans.size() - 1 ? "\n":" ");
        }
    }
}

多余的Delete操作没有删，源代码
其实只要将最小堆的插入删除创建写一遍就好了，这道题就迎刃而解了，我第一次提交没过，觉得可能是我数组定义小了，所以换成1000，还是没过，然后再换成1001，过了，所以最后一个测试点的数据大小应该是1000，因为我的IsFull()函数是判断m_h->size == m_h->capacity - 1，因为我们设置了哨兵，他也占了一个位置，哨兵的作用是为了再插入或者删除的循环体内让其达到边界就退出，不需要额外加一个i>0.