Complete min-heap binary tree

[Tuong_Le (Tường Lê)]

Chào mọi người, em đang làm bài dựng cái complete min-heap BT từ 1 cái vector, mà em đã thử các trường hợp em nghĩ ra, nhưng mà code của em nó vẫn còn sai gì đó. Mấy anh tinh mắt xem và gợi ý giúp em với ạ. Em xin cảm ơn nhiều lém
Output ra thứ tự của những cặp cần swap
VD:
5
5 4 3 2 1
Output:
3
1 4
0 1
1 3

#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class HeapBuilder {
private:
	vector<int> data_;
	vector< pair<int, int> > swaps_;

	void WriteResponse() const {
		cout << swaps_.size() << "\n";
		for (int i = 0; i < swaps_.size(); ++i) {
			cout << swaps_[i].first << " " << swaps_[i].second << "\n";
		}
	}

	void ReadData() {
		int n;
		cin >> n;
		data_.resize(n);
		for (int i = 0; i < n; ++i)
			cin >> data_[i];
	}

	void siftDown(int i, int a) {
		while (i <= a)
		{
			if (data_[i] > data_[2 * i + 1] && (2 * i + 2 > data_.size() - 1 || data_[i] < data_[2 * i + 2]))
			{
			swap(data_[i], data_[2 * i + 1]);
			swaps_.push_back(make_pair(i, 2 * i + 1));
			i = 2 * i + 1;
			}
			else if (data_[i] > data_[2 * i + 1] && data_[i] > data_[2 * i + 2])
			{
				if (data_[2 * i + 1] < data_[2 * i + 2])
				{
					swap(data_[i], data_[2 * i + 1]);
					swaps_.push_back(make_pair(i, 2 * i + 1));
					i = 2 * i + 1;
				}
				else
				{
					swap(data_[i], data_[2 * i + 2]);
					swaps_.push_back(make_pair(i, 2 * i + 2));
					i = 2 * i + 2;
				}
			}
			else if (data_[i] > data_[2 * i + 2]){
				swap(data_[i], data_[2 * i + 2]);
				swaps_.push_back(make_pair(i, 2 * i + 2));
				i = 2 * i + 2;
			}
			else
			{
				i = a + 1;
			}
		}
	}
	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.
		//
		// TODO: replace by a more efficient implementation
		for (int i = (data_.size() - 2) / 2; i >= 0; i--)
		{
			siftDown(i, (data_.size() - 2) / 2);
		}		
	}

public:
	void Solve() {
		ReadData();
		GenerateSwaps();
		WriteResponse();
	}
};

int main() {

	ios_base::sync_with_stdio(false);
	HeapBuilder heap_builder;
	heap_builder.Solve();
	return 0;

}

[tntxtnt]

nhớ code build heap gì đơn giản lắm mà sao ở đây phức tạp vậy :V

[Tuong_Le (Tường Lê)]

Ahihi, tại cái này em nghĩ tới đâu làm tới đó á, chứ chưa có coi pseudocode của bài này nên nó hơi sida :))))). Còn cái này là code xịn em mới coi, em đang chạy thử test case coi đúng ko.

int parent(int i)
	{
		return (i - 1) / 2;
	}
	int leftChild(int i)
	{
		return 2 * i + 1;
	}
	int rightChild(int i)
	{
		return 2 * i + 2;
	}
	void siftDown(int i) {
		if (i > (data_.size() - 2) / 2)
			return;
		int minIndex = i;
		int l = leftChild(i);
		if (l <= data_.size() - 1 && data_[l] < data_[minIndex])
			minIndex = l;
		int r = rightChild(i);
		if (r <= data_.size() - 1 && data_[r] < data_[minIndex])
			minIndex = r;
		if (i != minIndex)
		{
			swap(data_[i], data_[minIndex]);
			swaps_.push_back(make_pair(i, minIndex));
		}
		else minIndex = 2 * minIndex + 2;
		siftDown(minIndex);
	}
	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.
		//
		// TODO: replace by a more efficient implementation
		for (int i = (data_.size() - 2) / 2; i >= 0; i--)
			siftDown(i);
	}

[tntxtnt]

@Tuong_Le

else minIndex = 2 * minIndex + 2;
siftDown(minIndex);

chỗ này là sao đây :V

thuật toán chỉ gọi tiếp khi i != largest thôi mà

[Tuong_Le (Tường Lê)]

:))) em hiểu rồi, cảm ơn sự góp ý của anh nhiều. Còn bài ở trên là chịu luôn hả.

[tntxtnt]

bài nào nữa :V in ra index các cặp bị swap thì em làm đúng rồi :V

[Tuong_Le (Tường Lê)]

Ý em là cái cách đầu á, mà thôi nó nhức đầu quá, bỏ luôn đi :v