Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

tumpukan

Antrean tumpukan dan prioritas:

Antrian prioritas adalah tipe data abstrak, dan heap adalah struktur data, jadi heap bukan antrian prioritas. Heap adalah cara untuk mengimplementasikan antrian prioritas.
Ada banyak cara untuk mengimplementasikan antrian prioritas, seperti array dan daftar tertaut. Namun, implementasi ini hanya dapat menjamin bahwa salah satu operasi penyisipan dan penghapusan dapat diselesaikan dalam kompleksitas waktu O(1)O(1), sedangkan operasi lainnya harus diselesaikan dalam O(N)O(N) Selesai dalam waktu kompleksitas waktu. Heap dapat memungkinkan operasi penyisipan antrian prioritas diselesaikan dalam kompleksitas waktu O(log N)O(logN), dan operasi penghapusan diselesaikan dalam kompleksitas waktu O(log N)O(logN) .

Heap adalah pohon biner khusus yang memenuhi ketentuan berikut:

1. Pohon biner lengkap (node ​​disusun secara berurutan dari kiri ke kanan);
2. Nilai setiap node harus lebih besar atau sama dengan atau kurang dari atau sama dengan nilai node turunannya.

Fitur tumpukan:

1. Elemen dapat dimasukkan ke dalam heap dalam kompleksitas waktu O(logN);
2. Elemen dapat dihapus dari heap dalam kompleksitas waktu O(logN);
3. Nilai maksimum atau minimum dalam heap dapat diperoleh dalam kompleksitas waktu O(1).

Klasifikasi tumpukan:

Max heap: Nilai setiap node di heap lebih besar atau sama dengan nilai node turunannya. Elemen teratas (root node) dari max heap adalah nilai maksimum di heap.
Tumpukan minimum: Nilai setiap node di heap kurang dari atau sama dengan nilai node turunannya. Elemen teratas (simpul akar) dari min-heap adalah nilai minimum di heap.
Nomor node saat ini adalah i, nomor anak kiri adalah 2i, dan nomor anak kanan adalah 2i+1.

Kompleksitas waktu dan kompleksitas ruang

Sortir tumpukan

Teori: Pengurutan heap mengacu pada penggunaan struktur data heap untuk mengurutkan sekumpulan elemen yang tidak berurutan.

Langkah-langkah algoritma min-heap sort adalah sebagai berikut:

Tumpuk semua elemen ke dalam tumpukan minimum;
Keluarkan dan hapus elemen teratas dari heap, dan tempatkan elemen teratas dari heap di kumpulan data T yang menyimpan elemen yang dipesan;
Saat ini, heap akan disesuaikan dengan heap minimum yang baru;
Ulangi langkah 3 dan 4 hingga tidak ada elemen di heap;
Pada titik ini diperoleh kumpulan data baru T, yang elemen-elemennya diurutkan dari kecil ke besar.

Langkah-langkah algoritma max heap sort adalah sebagai berikut:

Tumpuk semua elemen ke dalam tumpukan maksimum;
Keluarkan dan hapus elemen teratas dari heap, dan tempatkan elemen teratas dari heap di kumpulan data T yang menyimpan elemen yang dipesan;
Saat ini, heap akan disesuaikan dengan heap maksimum yang baru;
Ulangi langkah 3 dan 4 hingga tidak ada elemen di heap;
Pada titik ini diperoleh kumpulan data baru T, yang elemen-elemennya diurutkan dari besar ke kecil.
Kompleksitas waktu: O(Nlog N). N adalah jumlah elemen di heap.

Kompleksitas ruang: O(N). N adalah jumlah elemen di heap.