Mengapa dua konsep berbeda disebut “heap”?

170

Mengapa tumpukan runtime digunakan untuk alokasi memori dinamis dalam bahasa gaya-C dan struktur data keduanya disebut "tumpukan"? Apakah ada hubungannya?

c++ heap terminology heap-memory Andrey Fedorov
sumber
4
Saya bertanya-tanya hari ini sambil mempelajari struktur data.
MitMaro
1
pertanyaan rangkap? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Buka kamus bahasa Inggris dan hitung jumlah entri di bawah "Jalankan". Berapa banyak dari 40 entri yang berlaku untuk komputer? :)
jmucchiello
2
kemungkinan duplikat Apa hubungan antara "a" heap dan "the" heap?
RCIX
Pos terkait di sini wrt heap heap digunakan untuk alokasi memori dinamis.
RBT

Jawaban:

77

Donald Knuth berkata (The Art of Computer Programming, Third Ed., Vol. 1, hal. 435):

Beberapa penulis mulai sekitar tahun 1975 menyebut kumpulan memori yang tersedia sebagai "tumpukan."

Dia tidak mengatakan penulis mana dan tidak memberikan referensi ke makalah tertentu, tetapi mengatakan bahwa penggunaan istilah "tumpukan" dalam kaitannya dengan antrian prioritas adalah pengertian tradisional dari kata tersebut.

James McNellis
sumber
11
Pool akan menjadi nama yang lebih baik daripada tumpukan.
7
Menarik. Seseorang harus bertanya kepadanya apakah dia ingat penulis mana.
Prof. Falken
27
Wikipedia mengklaim bahwa itu karena pada tahap awal Lisp menggunakan heap (struktur data) untuk mengimplementasikan penyimpanan memorinya. Itu tidak mengatakan bagaimana. Rujukannya adalah "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Pengantar algoritma. MIT Press / McGraw-Hill.", Yang tidak saya miliki.
Steve Jessop
2
Saya tidak punya referensi untuk ini, tetapi dugaan saya adalah bahwa awalnya struktur data yang digunakan untuk mengatur referensi untuk membuka blok memori adalah tumpukan min. Sepertinya itu akan menjadi setidaknya cara yang layak untuk dengan cepat menemukan blok memori terkecil yang akan memungkinkan Anda untuk menyimpan data yang Anda coba untuk menyimpan Pembaruan: Apa yang saya katakan terdengar persis seperti sobat blok en.wikipedia.org/wiki/Dynamic_memory_allocation # Buddy% 5Fblocks
Will
4
@SteveJessop - Memeriksa Cormen, Leiserson, Rivest, Stein - edisi ke-3 (2009) pada awal bab Heapsort hanya mengatakan 'Istilah "tumpukan" awalnya diciptakan dalam konteks heapsort, tetapi sejak itu merujuk pada " penyimpanan yang dikumpulkan sampah, "seperti bahasa pemrograman yang disediakan Java dan Lisp. Struktur data tumpukan kami bukan penyimpanan yang dikumpulkan dari sampah, dan setiap kali kami merujuk pada tumpukan dalam buku ini, kami akan mengartikan struktur data daripada aspek pengumpulan sampah. ' CLRS - edisi ke-2 juga memiliki frasa yang hampir sama (tidak ada indikasi bahwa Lisp menggunakan Heap).
dr jimbob
64

Mereka memiliki nama yang sama tetapi mereka benar-benar tidak mirip (bahkan secara konseptual). Tumpukan memori disebut tumpukan dengan cara yang sama Anda akan menyebut keranjang cucian sebagai "tumpukan pakaian". Nama ini digunakan untuk menunjukkan tempat yang agak berantakan di mana memori dapat dialokasikan dan dialokasikan sesuai keinginan. Struktur data (seperti yang ditunjukkan oleh tautan Wikipedia) sangat berbeda.

Andrew Hare
sumber
8
Ya, saya pikir itu adalah titik di mana dia mendasarkan pertanyaannya: mereka berbeda. Jadi mengapa mereka disebut hal yang sama - adakah hubungan yang mendasarinya?
Sean Owen
9
Cara saya menafsirkan jawaban ini adalah "tidak, tidak ada hubungan yang mendasarinya", jadi itu menjawab pertanyaan.
Laurence Gonsalves
Andrew menjawab itu. Tidak ada hubungannya. Hanya kebetulan. Tumpukan memori lebih benar untuk penggunaan umum karena memori dialokasikan seolah-olah "tumpukan pakaian". Namun struktur data menuntut imajinasi yang lebih besar. Dan ini menjadi "mengapa" yang jauh lebih menarik. Nama berasal dari simpul fakta yang diatur oleh kunci mereka dan kunci simpul orangtua selalu> = daripada simpul anaknya.
Alexandre Bell
6
Mereka jelas tidak berhubungan. Namun masalah dengan menyebutnya "heap" adalah "the heap's" counterpart - "the stack" - juga merupakan stack yang sebenarnya.
dan
1
Saya tahu mengapa struktur data tumpukan disebut tumpukan: karena memenuhi properti tumpukan. Tapi mengapa heap property disebut seperti itu? Tidak masuk akal bagi saya, karena nama seperti "top heavy" akan jauh lebih baik.
Thomas Eding
31

Tabrakan nama itu disayangkan, tetapi tidak semua yang misterius. Heap adalah kata kecil yang umum digunakan untuk tumpukan, kumpulan, grup, dll. Penggunaan kata untuk struktur data pra-tanggal (saya cukup yakin) nama kumpulan memori. Bahkan, kolam akan menjadi pilihan yang jauh lebih baik untuk yang terakhir, menurut pendapat saya. Heap berkonotasi struktur vertikal (seperti tumpukan), yang cocok dengan struktur data, tetapi tidak kumpulan memori. Kami tidak menganggap tumpukan kumpulan memori sebagai hierarki, sedangkan ide mendasar di balik struktur data adalah menjaga elemen terbesar di atas tumpukan (dan sub-tumpukan).

Tumpukan struktur data tanggal kembali ke pertengahan 60-an; menumpuk kumpulan memori, awal 70-an. Istilah heap (artinya kumpulan memori) digunakan setidaknya pada awal 1971 oleh Wijngaarden dalam diskusi tentang Algol.

Mungkin penggunaan heap paling awal sebagai struktur data ditemukan tujuh tahun sebelumnya di
Williams, JWJ 1964. "Algoritma 232 - Heapsort", Communications of the ACM 7 (6): 347-348

IJ Kennedy
sumber
1
Ya, tetapi tumpukan juga menyiratkan gangguan dan tumpukan memori pada umumnya tidak teratur. Tumpukan struktur data sangat tertata dengan baik. Jadi sekali lagi ada ketidakcocokan yang sama terjadi sebaliknya berdasarkan definisi umum heap.
jmucchiello
Itu selalu diperkenalkan sebagai kebalikan dari tumpukan yang cukup untuk menjelaskan nama IMO.
reinierpost
1
Ini bukan kebetulan - daftar gratis dapat diimplementasikan sebagai antrian prioritas melalui tumpukan binomial.
Heath Hunnicutt
2
@ jmucchiello: tumpukan log (lihat gambar ) tertata dengan baik dan menyerupai pohon. Ini adalah asal dari nama struktur data menurut salah satu buku teks sarjana saya.
gioele
6

Sebenarnya, membaca tentang cara memori dialokasikan (lihat Blok Buddy ) mengingatkan saya pada tumpukan dalam struktur data.

Bepergian Tek Guy
sumber
Komentar saya tentang jawaban Peter Zhang juga relevan di sini. Sistem buddy biner dapat direpresentasikan sebagai pohon biner, dan juga terlihat sebagai heap max valid ketika "kunci" dari setiap node adalah total memori di bawahnya (tetapi nilai-nilai ini implisit dan tidak pernah berubah). Alokasi atau algoritma pembebasan tidak menggunakan operasi tumpukan pada pohon biner ini, sejauh yang saya tahu.
Eric Dubé
5

IMO itu hanya kebetulan / kebetulan bahwa kedua hal yang sama sekali tidak berhubungan ini memiliki nama yang sama. Ini seperti grafik dan grafik .

MAK
sumber
Kedua grafik tersebut entah bagaimana dapat dihubungkan. Bayangkan grafik fungsi sebagai berikut: Domain tuple, range) adalah sebuah sudut dan tepi menghubungkan dua simpul seperti
2
@Amit: Untuk grafik kontinu yang berarti jumlah simpul yang tak terbatas. Ini ok, tapi itu juga membuat konsep tepi antara simpul tidak ada artinya. Dalam grafik fungsi f (x) = x * 2, apakah ada batas antara (0,0) dan (1,2)? Jika ya, bagaimana dengan (0,0) dan (0,5,1)? (0,0) dan (0,25,0,5)? Tidak ada cara untuk memiliki konsep tepi antara simpul, jadi ini bukan grafik.
MAK
5

Struktur data mirip tumpukan digunakan oleh algoritma untuk menemukan alokasi memori yang tersedia. Berikut ini adalah kutipan dari http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Ketika newdipanggil, ia mulai mencari blok memori gratis yang sesuai dengan ukuran permintaan Anda. Misalkan blok memori seperti itu ditemukan, itu ditandai sebagai dicadangkan dan pointer ke lokasi itu dikembalikan. Ada beberapa algoritma untuk mencapai hal ini karena kompromi harus dilakukan antara pemindaian seluruh memori untuk menemukan blok bebas terkecil lebih besar dari ukuran objek Anda, atau mengembalikan yang pertama di mana memori yang dibutuhkan cocok. Untuk meningkatkan kecepatan mendapatkan blok memori, area memori yang bebas dan dicadangkan dipertahankan dalam struktur data yang mirip dengan pohon biner yang disebut heap.

Peng Zhang
sumber
1
Saya sangat skeptis dengan hal ini, khususnya "... area memori yang bebas dan dicadangkan dipertahankan dalam struktur data yang mirip dengan pohon biner yang disebut heap." Kedengarannya bagi saya seperti penulis menebak ada koneksi, berdasarkan nama "tumpukan", dan mungkin salah. Adakah yang bisa mengkonfirmasi / membantah?
Don Hatch
1
Setelah beberapa penelitian ringan pada sistem Binary Buddy (digunakan di Linux), itu dapat diwakili oleh pohon biner karena bagaimana partisi data. Pohon biner ini terlihat seperti tumpukan maks yang valid jika Anda mengamati node dalam hal total memori, tetapi node tidak dimasukkan ke dalam pohon biner ini karena mereka berada di tumpukan max - node dimasukkan langsung ke dalam daun terkecil dari memori bebas> = ukuran yang diminta. 1 2 3
Eric Dubé
1

Istilah sehari-hari menumpuk memori dan memori tumpukan tidak digunakan dalam standar C ++. Standar ini menggunakan penyimpanan statis, penyimpanan utas, penyimpanan otomatis, dan penyimpanan dinamis.

Lebih banyak dapat ditemukan di bagian Duration Penyimpanan standar.

Oleh karena itu, dari sudut pandang bahasa dan perpustakaan standar, tidak ada kebingungan.

R Sahu
sumber
1

Q. Apa itu heap? A. Tumpukan adalah kumpulan objek yang saling bertumpukan.

Jawaban untuk pertanyaan Anda: Memori tumpukan dan tumpukan biner menggunakan konsep yang sama seperti yang Anda tahu. Data disimpan dalam bentuk tumpukan di memori dalam urutan yang sama seperti yang ditulis dalam program sedangkan tumpukan biner adalah struktur data yang mengikuti konsep yang sama menyimpan data dalam cara yang dipesan dalam bentuk tumpukan (Data di atas dari yang lain). Biarkan saya tahu apa yang Anda pikirkan di bagian komentar.

Mayank Tolani
sumber
-2

Mungkin tumpukan memori pertama diimplementasikan dikelola oleh struktur tumpukan?

Adam Maras
sumber
8
Hipotesis itu tampaknya sama sekali tidak jelas - bagaimana tumpukan (struktur data) sama sekali berguna untuk mempertahankan tumpukan (wilayah memori dinamis)?
Keith Randall
7
-1. Saya lebih suka pernyataan otoritatif dengan bukti daripada apa yang jelas hanya dugaan.
Rob Kennedy
Sangat tidak mirip. Tampaknya tidak ada alasan yang baik untuk menggunakan heap (struktur data) untuk mengelola heap (kumpulan memori bebas).
jason