Heap

·2023년 5월 31일
0

개발 지식

목록 보기
83/96
post-thumbnail

소개

완전 이진트리의 일종으로 우선수위 큐를 위해 만들어진 자료구조이다. 모든 노드에 대하여 부모와 자식간에 일정한 대소 관계가 성립한다. 부모가 자식보다 큰 값을 가지고 있다면 최대 힙, 작은 값을 가지고 있다면 최소 힙이라 표현한다. 전체 자료를 정렬하는 것이 아닌, 값 중에 가장 큰 값과 작은 값을 찾을 때 주로 사용된다.

Heap 기초 인덱스 알아두기

배열을 통해 Heap을 구현하는 경우, 루트 인덱스를 1 이라 한다면 부모와 자식 노드를 가진 임의의 노드 인덱스를 nn 이라 한다고 가정했을 때, 관련 노드의 인덱스는 다음과 같이 표현할 수 있다.

  • 부모 인덱스 : n/2n/2
  • 왼쪽 자식 인덱스 : n2n*2
  • 오른쪽 자식 인덱스 : n2+1n *2 +1

Heapify

우선순위 큐의 정렬 로직이며 O(logn)O(log n) 의 시간복잡도를 나타내는 핵심 원리로, 자식과 부모의 대소비교를 통해, 노드의 위치를 스왑하는 과정이다. 해당 원리는 새로운 노드를 삽입하는 경우와 노드를 반환(삭제) 하는 경우 일어난다.

  • 삽입 : 삽입하는 값을 먼저, 배열의 마지막 인덱스로 추가한다. 삽입한 리프 노드를 기준으로, 부모 노드와 대소비교를 통해 조건에 해당하는 경우, 부모-자식의 관계를 스왑한다.
  • 삭제 : 루트 노드의 값 (최소 혹은 최대) 을 제거하고, 맨 마지막 데이터를 루트노드로 옮긴 후, 부모 노드와 대소비교를 통해 조건에 해당하는 경우, 부모-자식 관계를 스왑한다.

프로세스 Heap

소개

프로세스를 실행하는 데 있어 메모리를 할당하는 한 부분이다. 주로 객체 인스턴스 및 리스트, 백터와 같은 동적 데이터를 저장하는데 많이 사용된다. 실제 값은 포인터 가 반영되며, 포인터가 가리키는 값은 스택에서 관리한다.

일반적으로 메모리 영역 가운데 가장 큰 공간을 점유하고 있으며, GC가 발생하는 곳이기도 하다.

브라우저 내부 구조

브라우저는 제품마다 조금씩 다르긴 하지만 여러개의 프로세스를 가지고 있다.

  • 브라우저 프로세스 : 주소 표시줄 북마크 막대, 뒤로 가기 버튼, 앞으로 가기 버튼 등을 담당하며, 네트워크 요청이나 파일 접근 같은 권한을 담당한다.
  • 렌더러 프로세스 : 웹사이트가 보여지도록 하는 부분의 모든 것을 담당한다.
  • 플러그인 프로세스 : 웹사이트에서 사용하는 플러그인을 담당한다.
  • GPU 프로세스 : 렌더링 시 GPU를 사용하여 화면을 그리는 부분을 제어한다.

프로세스의 Heap과 자료구조 Heap의 차이

둘은 이름만 같을 뿐 젼혀 다른 기술이라고 한다.

profile
새로운 것에 관심이 많고, 프로젝트 설계 및 최적화를 좋아합니다.

0개의 댓글