Hoi ve heap sort

[songok]

Xin cho hoi mot day so thoa dieu kien : a(i) > a(3i*), a(3*i+1), a(3*i+2);thi co duoc goi la mot heap hay ko ?
Co the ap dung thuat toan heap sort de ap dung cho mot day so nhu tren khong ?

Vui lòng gửi bài viết bằng tiếng Việt có dấu - vikhoa

[bete]

Theo tui nghĩ: nếu cài đặt heap sort dùng mảng thì tại bất cứ node nào: gốc sẽ ở chỉ số i, gốc của cây con trái (nếu có) sẽ ở chỉ sồ 2i, gốc của cây con phải (nếu có) sẽ ở chỉ số 2i+1 . Và nếu là heap thì phải thỏa điều kiện: ở MỌI cây con (mọi node): giá trị chứa tại gốc phải lớn hơn hay bằng MỌI giá trị chứa trong 2 cây con (nếu tui 0 lầm thì có một dạng tương tự: ở MỌI cây con (mọi node): giá trị chứa tại gốc phải nhỏ hơn hay bằng MỌI giá trị chứa trong 2 cây con )

Có vẻ cái mảng của bạn 0 thỏa điều kiện này ?

(a[i] >= a[2i]
a[i] >= a[2i+1]
a[i] >= a[4i]
a[i] >= a[4i+1]
a[i] >= a[4i+2]
a[i] >= a[4i+3]
a[i] >= a[8i]
a[i] >= a[8i+1]
a[i] >= a[8i+2]
..................
a[i] >= a[8i+7]
............
)

[ttranthien]

Cấu trúc Heap được xây dựng dựa trên cấu trúc cây nhị phân đầy đủ và thường dùng mảng để minh họa. Điều kiện bạn nêu ra cho một mảng không phải là một cấu trúc Heap theo định nghĩa truyền thống. Theo tôi việc dùng cấu trúc của bạn có thể thực hiện sắp xếp tương tự như thuật toán HeapSort nhưng không cải tiến được gì trong trường hợp tổng quát.

[anhunsw]

Toi chi bo sung them 1 ty,

Ban luu y, co 2 loai Heap: Min_Heap va Max_Heap. Simply put, Min _heap se co Child >= parent, ve nguoc lai cho Max_heap

Neu ban dung array de luu heap, ban nen BO, khong dung index 0, ma assign cho root index 1...

Heap khong kho, vi vay ban hay search google voi keywords HeapSort, HeapifyUp. HeapifyDown...

Khong biet y kien tren co giup duoc ban chuc nao khong.

Than ,
Anh