Heap Sort - Thuật Toán Sắp Xếp Vun Đống

Giải thuật sắp xếp Heapsort (Heap sort) được đề xuất vào năm 1964 bởi J. W. J. Williams. Cùng năm đó, R. W. Floyd đã đưa ra phiên bản cải tiến của thuật toán này giúp nó trở thành thuật toán in-place với thời gian thực thi nhanh và độ phức tạp trong trường hợp xấu nhất là O(n log n).

Giải thuật Heapsort

Giải thuật Heapsort còn được gọi là giải thuật vun đống, có thể được xem như bản cải tiến của Selection Sort khi chia các phần tử thành 2 mảng con.

• 1 mảng các phần tử đã được sắp xếp.
• 1 mảng các phần tử chưa được sắp xếp.

Trong mảng chưa được sắp xếp, các phần tử lớn nhất sẽ được tách ra và đưa vào mảng đã được sắp xếp. Điều cải tiến ở Heapsort so với Selection Sort ở việc sử dụng cấu trúc dữ liệu heap thay vì tìm kiếm tuyến tính (linear-time search) như Selection sort để tìm ra phần tử lớn nhất.

Heapsort là thuật toán in-place, nghĩa là không cần thêm bất cứ cấu trúc dữ liệu phụ trợ trong quá trình chạy thuật toán. Tuy nhiên, giải thuật này không có độ ổn định (stability).

Các bước thực hiện

Giải thuật Heapsort được chia thành 2 giai đoạn.

Giai đoạn 1

Từ dãy dữ liệu input, sắp xếp chúng thành một heap (dạng cấu trúc cây nhị phân). Heap này có thể là Min-heap (nút gốc có giá trị bé nhất) hoặc Max-heap (nút gốc có giá trị lớn nhất), trong bài viết này, ta sẽ sử dụng Max-heap với một số yêu cầu thỏa mãn sau:

• Nút cha sẽ luôn lớn hơn tất cả các nút con, nút gốc của heap sẽ là phần tử lớn nhất.
• Heap được tạo thành phải là một cây nhị phân đầy đủ, tức ngoại trừ các nút lá, ở cùng một cấp độ các nút nhánh không được thiếu.

Giai đoạn 2

Giai đoạn này gồm các thao tác được lặp đi lặp lại cho đến khi mảng dữ liệu được toàn tất sắp xếp:

• Đưa phần tử lớn nhất của heap được tạo vào mảng kết quả, mảng này sẽ chứa các phần tử đã được sắp xếp.
• Sắp xếp lại heap sau khi loại bỏ nút gốc (có giá trị lớn nhất) để tìm phần tử có giá trị lớn nhất tiếp theo.
• Thực hiện lại thao tác 1 cho đến khi các phần tử của heap đều được đưa vào mảng kết quả.

Như thế, mảng kết quả sẽ chứa các phần tử được sắp xếp giảm dần.

Hiện thực Heapsort

Hàm createHeap sẽ tạo heap từ dữ liệu đưa vào là mảng và kích thước mảng. Sử dụng vòng lặp tính từ vị trí giữa mảng, createHeap sẽ lặp và sắp xếp các phần tử để tạo nên heap thỏa mãn các tính chất cần thiết bằng hàm heapify.

void createHeap(int *_array, int _length)
{
	int offset, heapSize;
	heapSize = _length - 1;

	for (offset = (_length / 2); offset >= 0; offset--)
	{
		heapify(_array, offset, heapSize);
	}
}

Hàm heapify sẽ kiểm tra nút trái, nút phải và nút ngay tại vị trí offset để tìm ra nút có giá trị lớn nhất. Trong trường hợp nút có giá trị lớn nhất không phải nút ở vị trí offset, hàm sẽ đổi giá trị 2 nút này và tiếp tục đệ quy heapify từ vị trí nút có giá trị lớn nhất để đi đến các nhánh tiếp theo để đảm bảo nút cha sẽ luôn có giá trị lớn hơn các nút con.

void heapify(int *_array, int _offset, int _heapSize)
{
	int leftNode, rightNode, largest, temp;
	leftNode = 2 * _offset;
	rightNode = 2 * _offset + 1;
	
	if (leftNode <= _heapSize && _array[leftNode] > _array[_offset])
	{
		largest = leftNode;
	}
	else
	{
		largest = _offset;
	}

	if (_array[rightNode] > _array[largest] && rightNode <= _heapSize)
	{
		largest = rightNode;
	}
	
	if (largest != _offset)
	{
		temp = _array[_offset];
		_array[_offset] = _array[largest];
		_array[largest] = temp;
		heapify(_array, largest, _heapSize);
	}
}

Cuối cùng, hàm heapSort sẽ nhận dữ liệu vào là mảng và kích thước, sử dụng vòng lặp từ vị trí _length - 1 để tiến hành hoán đối giá trị các phần tử. Sau mỗi vòng lặp hàm sẽ giảm heapSize xuống 1 và sắp xếp lại heap.

void heapSort(int *_array, int _length)
{
	createHeap(_array, _length);

	int heapSize, offset, temp;
	heapSize = _length - 1;
	
	for (offset = heapSize; offset >= 0; offset--)
	{
		temp = _array[0];
		_array[0] = _array[heapSize];
		_array[heapSize] = temp;

		heapSize--;

		heapify(_array, 0, heapSize);
	}

	for (offset = 0; offset < _length; offset++)
	{
		cout << " " << _array[offset];
	}
}

Dù tốc độ chạy của Heapsort có đôi chút chậm hơn Quick Sort, nhưng bù lại Heapsort là giải thuật đảm bảo trong trường hợp xấu nhất, độ phức tạp giải thuật cũng là O(n log n). Giải thuật này cũng không cần thêm các cấu trúc dữ liệu phụ trợ trong quá trình thực thi, do đó sẽ có tốc độ nhanh và thường được sử dụng rộng rãi do không khó để hiện thực.