Cormen의 힙 정렬 구조

Question

나는 Cormen의 알고리즘 책의 힙 정렬 장을 갈거야하지만 문 아래 이해 붙어있어

:

대부분의 컴퓨터에

, 왼쪽 절차를 하나의 비트 위치 인 에 의해 왼쪽 i의 이진 표현을 단순히 시프트함으로써 하나의 명령에서 2i를 계산할 수 있습니다.

마찬가지로 RIGHT 프로시 저는 을 1 비트 위치만큼 왼쪽으로 이진 표현으로 바꾼 다음 을 하위 비트로 1을 더함으로써 빠르게 2i + 1을 계산할 수 있습니다. PARENT 프로 시저는 오른쪽 1 비트 위치를 시프트함으로써 [i/2]을 계산할 수 있습니다. heapsort의 좋은 구현은 종종 이러한 절차를 "매크로"또는 "인라인"절차 절차로 구현합니다.

여기서 LEFT 절차는 무엇이며 계산 방법은 무엇입니까?

마찬가지로 오른쪽 절차의 계산 방법은 & 학부모입니다.

매크로 또는 인라인 프로 시저를 사용하여 프로 시저를 구현한다는 것을 의미합니다.

많은 사람들로부터 알고리즘을 배우는 데 가장 좋은 책이라는 것을 알게되었지만 저자가 여기서 설명하려고하는 것을 이해할 수 없습니다.

Answer 1

parent, left 및 right 절차는 간단합니다 (i에) 주어진 parent, left 및 right 요소를 얻기위한 계산.

부모이 i/2

왼쪽의 바닥입니다 2i

오른쪽2i + 1

---

이 제공 한 예를 살펴입니다. 일반적으로 배열은 0을 기반으로하지만 예제는 1을 기준으로합니다.

배열이 있으니 A라고 부릅니다. 여기서 A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]입니다.

의 우리가 위의 계산을 사용하여 10 입니다 A[3]에서 찾고 있다고 가정 해 봅시다, A[3]의 부모는 A[1]이다 (16) A[3] 의 왼쪽 아이가 9 A[3]의 권리 아이입니다 A[6]입니다 i가 하나의 비트 위치만큼 왼쪽으로 대부분의 시스템에서 3

---

이다 A[7]는 LEFT 절차는 단순히 이진 표현을 이동함으로써 하나의 명령에 2I를 계산할 수 .

마찬가지로 RIGHT 프로시 저는 1 비트 위치만큼 왼쪽의 2 진 표현을 시프트 한 다음 하위 비트로 1을 더함으로써 2i + 1을 빠르게 계산할 수 있습니다. PARENT 프로시 저는 i를 오른쪽으로 1 비트 이동시켜 [i/2]를 계산할 수 있습니다. heaport의 좋은 구현은 종종 이러한 절차를 "매크로"또는 "인라인"절차로 구현합니다.

이것은 프로세서 수준에서 이러한 기능의 복잡성을 설명합니다. 요점은 parent, left 및 right은 일반적으로 프로세서에서 하나 또는 두 개의 명령으로 실행될 수 있다는 것입니다.

inline procedures에 대한 의견은 컴파일러 최적화를 설명합니다. 컴파일러는 대개 어셈블리 코드를 작성하는 경우 인간보다 더 많은 어셈블리 명령어를 생성합니다. 따라서이 주석은 올바른 컴파일러 최적화를 사용할 수 있다고 가정하고 (parent, left 및 right) 프로 시저를 단일 (또는 몇 가지) 명령으로 컴파일 할 수 있다는 것을 말하는 것입니다.

이러한 절차가 실제로 프로세서 수준에서 실행되는 방법을 이해하려는 경우 약 bit shifting을 읽거나 다른 대답을 읽을 수 있습니다.

Answer 2

노드 # 2의 이진 표현을 보면 0000 0010입니다 (가독성을 위해 4 비트로 나눕니다). 왼쪽 쉬프트는 모든 비트가 왼쪽 비트를 대신한다는 것을 의미하며, 오른쪽 이웃 비트가없는 모든 비트는 0이됩니다.

따라서 0000 0001에는 0000 0010이 표시되고 노드 # 2는 0000 0100이 될 것입니다. 가장 오른쪽 비트가 이제 0 인 것을 보았습니까? 또한 바이너리 표현 0000 0100은 4이며 노드 2의 왼쪽 하위 노드와 정확히 같은 번호가 있습니다.

이해한다면 나머지는 쉽습니다. +1이있는 왼쪽 쉬프트는 0000 0010 (2)를 0000 0101 (5)로 변경합니다. 그래서 이것은 올바른 아이의 노드 번호입니다.

표현에서 무엇인가를 잘라 내기 때문에 좀 더 까다로운 것이 부모입니다. 노드 # 3 0000 0011의 부모를 얻으려는 경우 오른쪽으로 한 번 이동하여 0000 0001 (1)이됩니다. 이것은 가장 오른쪽 비트가 잘리지 않으므로 두 어린이 모두에게 적용됩니다.

매크로로 바로 & 인라인. 인라인은 일부 프로그래밍 언어의 메소드입니다 (예 : C++로 배웠습니다). 컴파일러에게 주어진 작업을 빠르게 처리 할 수 ​​있는지 평가해야한다고 알려줍니다. 이것은 자주 발생하는 매우 간단한 작업에도 유용합니다 (왼쪽 Shift & 오른쪽 작업 임). 이러한 기본 알고리즘은 처리해야하는 노드가 많을수록 속도가 느려질 것이므로 매우 효율적이어야합니다. 매크로는 거의 동일하며 여러 번 실행되는 작업을 저장합니다.당신이 더 잘 이해하기 위해 구글 수

일부 문구 : 왼쪽 시프트 비트 연산 인라인 방법 C++

최고의 소원,

ESSI