왜 두 가지 다른 개념이 "힙"이라고 불리는가?
https://stackoverflow.com/questions/1699057
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
런타임 힙이 C 스타일 언어로 동적 메모리 할당에 사용되는 이유 데이터 구조 둘 다 "힙"이라고 불렀습니까? 관계가 있습니까?
해결책
Donald Knuth는 (컴퓨터 프로그래밍의 예술, 제 3의 vol. 1, p. 435) :
몇몇 저자들은 1975 년경에 가용 메모리 풀을 "힙"이라고 부르기 시작했습니다.
그는 어떤 저자를 말하지 않고 특정 논문에 대해 언급하지 않지만 우선 순위 대기열과 관련하여 "힙"이라는 용어의 사용은 단어의 전통적인 의미라고 말합니다.
다른 팁
그들은 같은 이름을 가지고 있지만 실제로는 비슷하지 않습니다 (개념적으로도). 메모리 힙을 세탁 바구니를 "옷 더미"라고하는 것과 같은 방식으로 힙이라고합니다. 이 이름은 메모리를 마음대로 할당하고 거래 할 수있는 다소 지저분한 장소를 나타내는 데 사용됩니다. 데이터 구조 (Wikipedia 링크가 참조하는 것처럼)는 상당히 다릅니다.
이름 충돌은 불행하지만 신비한 것은 아닙니다. 더미 파일, 수집, 그룹 등을 의미하는 데 사용되는 작고 일반적인 단어입니다. 데이터 구조 프리 데이트에 대한 단어 사용 (확실한) 메모리 풀의 이름. 사실로, 수영장 제 생각에는 후자에게 훨씬 더 나은 선택이었을 것입니다. 더미 데이터 구조에 맞지 만 메모리 풀이 아닌 수직 구조 (파일과 같은)를 포함합니다. 우리는 메모리 풀 힙을 계층 적으로 생각하지 않지만, 데이터 구조의 기본 아이디어는 가장 큰 요소를 힙 상단 (및 하위 해적)에 유지하는 것입니다.
데이터 구조는 60 년대 중반으로 거슬러 올라갑니다. 메모리 풀, 70 년대 초. 힙 (메모리 풀 의미)이라는 용어는 적어도 1971 년 초에 사용되었습니다. Wijngaarden Algol의 토론에서.
아마도 가장 초기의 사용 더미 7 년 전에 데이터 구조가 발견됨에 따라
Williams, JWJ 1964. "알고리즘 232- Heapsort", ACM의 통신 7(6): 347-348
실제로, 메모리가 할당되는 방식에 대해 읽는다 ( 버디 블록) 데이터 구조의 힙을 상기시켜줍니다.
힙과 같은 데이터 구조는 사용 가능한 메모리 할당을 찾는 알고리즘에 의해 사용됩니다. 다음은 발췌 한 내용입니다 http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.
언제
new호출됩니다. 요청 크기에 맞는 무료 메모리 블록을 찾기 시작합니다. 그러한 메모리 블록이 발견된다고 가정하면, 예약 된 것으로 표시되고 해당 위치에 대한 포인터가 반환됩니다. 객체의 크기보다 더 큰 프리 블록을 더 크게 찾기 위해 전체 메모리를 스캔하거나 메모리가 필요한 첫 번째 제품을 반환하는 것 사이에 타협해야하기 때문에이를 달성하기위한 여러 알고리즘이 있습니다. 메모리 블록을 얻는 속도를 향상시키기 위해, 무료 및 예약 된 메모리 영역은 힙이라고 불리는 이진 트리와 유사한 데이터 구조로 유지됩니다.
구어체 용어 스택 메모리 및 힙 메모리는 C ++ 표준에서 사용되지 않습니다. 표준은 정적 스토리지, 스레드 스토리지, 자동 스토리지 및 동적 스토리지를 사용합니다.
더 많은 것을 찾을 수 있습니다 저장 기간 섹션 표준의.
따라서 언어와 표준 라이브러리 관점에서 혼란이 없습니다.
Q. 힙은 무엇입니까? A. 힙은 서로 위에있는 물체의 모음입니다.
질문에 대한 답변 : 메모리 힙과 이진 힙은 알고있는 것과 동일한 개념을 사용합니다. 데이터는 프로그램에 작성된 것과 동일한 순서로 메모리의 힙 형태로 저장되는 반면, 이진 힙은 힙 형태로 순서대로 데이터를 저장하는 것과 동일한 개념을 따르는 데이터 구조입니다 (상단의 데이터. 다른 쪽). 의견 섹션에서 어떻게 생각하는지 알려주세요.
구현 된 첫 번째 메모리 힙은 힙 구조에 의해 관리되었을 것입니까?
