Heap data structure

[forrest_1001]

Có bạn nào biết cách tạo cấu trúc dữ liệu Binary Heap bằng ngôn ngữ Java thì chỉ cho mình với. Hay có mã nguồn thì cho mình xin cũng được.
Cám ơn nhiều.

[no9]

Bạn có thể dùng tạm code của C++, cũng gần như giống hệt Java. Cấu trúc Heap là cấu trúc có 2 tính chất:
- Giá trị của parent node lớn hơn 2 child nodes.
- Là complete binary tree, và mọi nodes thiếu đều nằm ở dưới cùng bên phải.

void array_list::fixHeap(int heapsize, int root, int k)
{
	if (2*root+1 > heapsize) // the root has no child
		a[root] = k;
	else {
		int largerSubHeap;
		if (2*root+1 == heapsize) // the root has 1 child
			largerSubHeap = 2*root+1;
		else // the root has 2 children
			largerSubHeap = (a[2*root+1] > a[2*root+2]) ? (2*root+1) : (2*root+2);
		if (k >= a[largerSubHeap])
			a[root] = k;
		else {
			a[root] = a[largerSubHeap];
			fixHeap(heapsize, largerSubHeap, k);
		}
	}
}

void array_list::constructHeap(int root)
{
	int k = a[root];
	
	if (2*root+1 >= num) // the root has no child
		return;
	else if (2*root+2 == num) // the root has 1 child
		constructHeap(2*root+1);
	else { // the root has 2 children
		constructHeap(2*root+1);
		constructHeap(2*root+2);
	}

	fixHeap(num, root, k);
}

void array_list::heapSort(void)
{
	int heapsize;

	constructHeap(0);
	for (heapsize = num; heapsize >= 2; heapsize--) {
		int currentMax = a[0];
		int k = a[heapsize-1];
		fixHeap(heapsize-1,0, k);
		a[heapsize-1] = currentMax;
	}
}

[forrest_1001]

Hihi..cam on No9 nhieu ha. A, cho minh hoi them, ban co biet cach tao Heap ma dung bo nho dong khong, giong nhu Linked List a, khong dung array ? Neu biet thi chi minh ha.
Thanks ..

[no9]

Ý tưởng của việc implement Priority Queue ở trên, dùng Heap là bạn sắp xếp lại các phần tử có sẵn trong một mảng thành một cái Heap "tưởng tượng". Mấu chốt là hàm fixHeap, dùng để điều chỉnh heap lại theo đúng định nghĩa.

Nếu bạn muốn implement bằng bộ nhớ động, bạn nên chỉnh sửa một chút từ cái implement của Binary Search Tree, mấu chốt quan trọng vẫn là fixHeap. Có điều, vì bạn lưu dữ liệu ban đầu (mảng cần chuyển thành Priority Queue) trong một array, nên đối với cấu trúc mới này, bạn không thể thay đổi cách sắp xếp các phần tử được. Bạn cần sửa lại hàm insert, trong đó, với mỗi phần tử mới chuẩn bị insert, bạn đi tìm vị trí cho nó theo cách của Heap thay vì cách của Binary Search Tree.

Hiện nay mình khá bận, có lẽ đến cuối tuần mới có thời gian để làm.