From 8047395062ce2234a94e35dadf11d8f29ecfb2ac Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Tue, 19 Feb 2019 22:17:57 -0600 Subject: Build heap done! It turned out it's more challenging converting Java code to C++ this time. The for loop, commented in the code, was tricky! The while loop was better anyway. It was good practice of doing debugging with gdb. Once again, rewarding experience!--- Sources/DataStructure.cpp | 217 +++++++++++++++++++++------------------------- 1 file changed, 97 insertions(+), 120 deletions(-) diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index e76d5be..f3d46be 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,141 +1,118 @@ #include -#include #include +#include //#include -struct Request { - Request(int arrival_time, int process_time) : - arrival_time(arrival_time), process_time(process_time) { - } +using std::vector; +using std::cin; +using std::cout; +using std::swap; +using std::pair; +using std::make_pair; - int arrival_time; - int process_time; -}; +class HeapBuilder { +private: + vector data_; +// vector > swaps_; + +// void GenerateSwaps() { +// swaps_.clear(); +// // The following naive implementation just sorts +// // the given sequence using selection sort algorithm +// // and saves the resulting sequence of swaps. +// // This turns the given array into a heap, +// // but in the worst case gives a quadratic number of swaps. +// // +// for (size_t i = 0; i < data_.size(); ++i) +// for (size_t j = i + 1; j < data_.size(); ++j) { +// if (data_[i] > data_[j]) { +// swap(data_[i], data_[j]); +// swaps_.push_back(make_pair(i, j)); +// } +// } +// } -struct Response { - Response(bool dropped, int start_time) : - dropped(dropped), start_time(start_time) { +public: + vector> swaps; + void WriteResponse() const { + cout << swaps.size() << "\n"; + for (size_t i = 0; i < swaps.size(); ++i) { + cout << swaps[i].first << " " << swaps[i].second << "\n"; + } } - bool dropped; - int start_time; -}; - -class Buffer { -public: - Buffer(int capacity) : - capacity_(capacity), finish_time_() { + void ReadData() { + int n; + cin >> n; + data_.resize(n); + for (int i = 0; i < n; ++i) + cin >> data_[i]; } - Response Process(const Request &request) { - // write your code here - if (runningTimeCounter_ < request.arrival_time) { - if (finish_time_.size() == 0) - runningTimeCounter_ = request.arrival_time; - else if (finish_time_.back() < request.arrival_time) - runningTimeCounter_ = request.arrival_time; + // Please note the for loop below. Initially I copied the for loop from my + // Java code, but it doesn't work in C++. Changing it to while loop worked! + // It was better with the while loop anyway, much clearer to me. + void UpdateSwaps(vector &data) { + int j = (data.size() - 1) / 2; + while (j >= 0) { + siftDown(j, data); + j = j - 1; } - while (finish_time_.size() > 0) { - int j = finish_time_.front(); - if (j <= request.arrival_time) - finish_time_.pop(); - else - break; - } - - if (finish_time_.size() >= capacity_) { - return Response(true, -1); +// for (size_t i = j; i >= 0; i--) { +// siftDown(i, data); +// } + } + void siftDown(int i, vector &data) { + int maxIndex = i; + size_t l = 2 * i + 1; + if (l < data.size() && data[l] < data[maxIndex]) + maxIndex = l; + size_t r = 2 * i + 2; + if (r < data.size() && data[r] < data[maxIndex]) + maxIndex = r; + if (i != maxIndex) { + swap(data[i], data[maxIndex]); + swaps.push_back(make_pair(i, maxIndex)); + siftDown(maxIndex, data); } - Response response = Response(false, runningTimeCounter_); - runningTimeCounter_ = runningTimeCounter_ + request.process_time; - if (finish_time_.size() > 0) - finish_time_.push(finish_time_.back() + request.process_time); - else - finish_time_.push(runningTimeCounter_); - return response; - } -private: - size_t capacity_; - std::queue finish_time_; - int runningTimeCounter_ = 0; -}; - -std::vector ReadRequests() { - std::vector requests; - int count; - std::cin >> count; - for (int i = 0; i < count; ++i) { - int arrival_time, process_time; - std::cin >> arrival_time >> process_time; - requests.push_back(Request(arrival_time, process_time)); + void Solve() { + ReadData(); +// GenerateSwaps(); + UpdateSwaps(data_); + WriteResponse(); } - return requests; -} - -std::vector ProcessRequests(const std::vector &requests, - Buffer *buffer) { - std::vector responses; - for (size_t i = 0; i < requests.size(); ++i) - responses.push_back(buffer->Process(requests[i])); - return responses; -} +}; -void PrintResponses(const std::vector &responses) { - for (size_t i = 0; i < responses.size(); ++i) - std::cout << (responses[i].dropped ? -1 : responses[i].start_time) - << std::endl; +int main() { +// vector data = { 5, 4, 3, 2, 1 }; +// HeapBuilder heap_builder; +// heap_builder.UpdateSwaps(data); +// heap_builder.WriteResponse(); + + std::ios_base::sync_with_stdio(false); + HeapBuilder heap_builder; + heap_builder.Solve(); + return 0; } -//TEST(ProcessRequests, t) { -// int bufferMaxSize = 1; -// Buffer buf = Buffer(bufferMaxSize); -// std::vector requests; -// std::vector responses = ProcessRequests(requests, &buf); -// ASSERT_EQ(0, responses.size()); -//} -// -//TEST(ProcessRequests, t1) { -// int bufferMaxSize = 1; -// Buffer buf = Buffer(bufferMaxSize); -// std::vector requests = {Request(0, 1)}; -// std::vector responses = ProcessRequests(requests, &buf); -// ASSERT_EQ(1, responses.size()); -// ASSERT_EQ(false, responses[0].dropped); +//TEST(BuildHeap, t) { +// vector data = {5, 4, 3, 2, 1}; +// HeapBuilder heap_builder; +// heap_builder.UpdateSwaps(data); +// ASSERT_EQ(3, heap_builder.swaps.size()); +// ASSERT_EQ(1, heap_builder.swaps[0].first); +// ASSERT_EQ(4, heap_builder.swaps[0].second); +// ASSERT_EQ(0, heap_builder.swaps[1].first); +// ASSERT_EQ(1, heap_builder.swaps[1].second); +// ASSERT_EQ(1, heap_builder.swaps[2].first); +// ASSERT_EQ(3, heap_builder.swaps[2].second); //} // -//TEST(ProcessRequests, t2) { -// int bufferMaxSize = 1; -// Buffer buf = Buffer(bufferMaxSize); -// std::vector requests = {Request(0, 1), Request(0, 1)}; -// std::vector responses = ProcessRequests(requests, &buf); -// ASSERT_EQ(2, responses.size()); -// ASSERT_EQ(false, responses[0].dropped); -// ASSERT_EQ(0, responses[0].start_time); -// ASSERT_EQ(true, responses[1].dropped); +//TEST(BuildHeap, t1) { +// vector data = {1, 2, 3, 4, 5}; +// HeapBuilder heap_builder; +// heap_builder.UpdateSwaps(data); +// ASSERT_EQ(0, heap_builder.swaps.size()); //} // -//TEST(ProcessRequests, t3) { -// int bufferMaxSize = 1; -// Buffer buf = Buffer(bufferMaxSize); -// std::vector requests = {Request(0, 1), Request(1, 1)}; -// std::vector responses = ProcessRequests(requests, &buf); -// ASSERT_EQ(2, responses.size()); -// ASSERT_EQ(false, responses[0].dropped); -// ASSERT_EQ(0, responses[0].start_time); -// ASSERT_EQ(false, responses[1].dropped); -// ASSERT_EQ(1, responses[1].start_time); -//} - -int main() { - int size; - std::cin >> size; - std::vector requests = ReadRequests(); - - Buffer buffer(size); - std::vector responses = ProcessRequests(requests, &buffer); - - PrintResponses(responses); - return 0; -} - -- cgit v1.2.3