Heap4 #06 힙 정렬(Heap Sort) 2021.12.31 - [Comuter Science/Data Structure] - 힙 자료구조 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 힙 자료구조는 트리를 기반으로 설계된 자료구조이다. 힙 정렬은 어떤 max 값을 꺼내고 다시 정렬하는 데에 O(logn)의 시간 복잡도가 소요된다. 이를 활용해서 n개의 원소를 매번 logn을 통해 불러오므로 O(nlogn)의 시간이 소요되는 정렬 알고리즘이다. 1. 주어진 배열을 최대 힙으로 만든다(heapify) 2. n번만큼 반복하며 루트 노드와 맨 끝 노드를 바꾼 .. 2022. 1. 7. 힙 자료구조 - insert 연산 1. 힙의 모양성질 만족 2. 모든 부모의 key가 자식의 key 보다 커야함 이러한 힙에서 만약 14가 들어오고자 하면, 새로 들어온 14 때문에 힙 성질을 만족하지 못한다. 따라서 이를 적절히 변경해줘야 함. 14를 위로 올려 보내면서 자기 자리를 찾도록 해야 한다. def insert(14): A.append(14) A.heapify(9) # up # A[k]를 root 방향으로 이동하면서 heapify def heapify(k): # A[k]를 heapify # 아직 루트에 도달하지 않았고, 부모의 key 값이 나보다 작을 때 while k > 0 and A[(k-1)//2] < A[k] : A[k], A[(k-1)//2 = A[(k-1)//2], A[k] k = (k-1)//2 참조 - http.. 2022. 1. 1. 힙 자료구조 - make heap 연산 https://hkim-data.tistory.com/187 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 이전 포스팅에 이어서 make heap 연산에 대해 알아보자 힙 성질을 만족하기 위해, heapify - down을 계속해서 진행하면 된다. 리스트의 맨 오른쪽 인덱스부터 A[0]까지 계속해서 반복 1. 리프노드면 내버려둠 2. 자식 노드가 있을 때 나보다 클 때 A [2*k+1]과 A [2*k+2] 값 중 큰 것이랑 변경 3. 변경 후 리프 노드가 아니면 또 아래랑 비교해줘야 함 def make_heap(A.. 2022. 1. 1. #3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + hkim-data.tistory.com 이전 포스팅에 이어 이제 실제 Stack과 Heap 메모리에서 어떻게 동작하는지 알아보자. 백그라운드 메모리 구성은 모든 프로세스가 일부 메모리와 함께 운영 체제에 의해 할당된다. 마찬가지로 python 인터프리터는 실행을 위해 메모리를 할당받는데, 이는 파이썬의 버전.. 2021. 12. 29. 이전 1 다음
