Algorithm/Data Structure (2) 썸네일형 리스트형 [Data Structure / JS] 이진 힙(Binary Heaps) / 우선순위 큐(Priority Queue) 힙(Heap)이란 ? 완전 이진트리 기반의 자료구조로, 최대 힙과, 최소 힙 두 종류로 구분됩니다. 최대 힙의 경우에는 루트노드에 가까울 수록 크고, 최소힙은 루트 노드에 가까울 수록 작은 값을 가집니다. 힙에서는 데이터의 중복이 허용되며, 주로 우선순위 큐를 구현하는데 사용됩니다. 나아가 힙 정렬, 다익스트라의 최단 경로 알고리즘에서도 사용됩니다. 힙은 부모자식간의 크기 차이만 비교합니다. 형제 노드 간에의 크기 차이를 고려하지 않습니다. 구현 힙은 일반적으로 각 요소에 효율적으로 접근할 수 있는 배열을 통해 구현됩니다. 인덱스 i에 위치한 노드의 부모는 (i-1)/2에 위치하며, 왼쪽 자식 노드는 2*i + 1, 오른쪽자식 노드는 2*i + 2에 위치하게 됩니다. Heap에서의 삽입 힙에서의 삽입은 .. [Data Structure / JS] 연결 리스트 연결리스트 ? 연결리스트는 선형 구조로서 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 입니다. 배열이라는 편리한 자료구조가 자바스크립트에서 제공이 되지만 왜 연결리스트가 필요할까 라는 의문이 들 수 있습니다. 배열과 연결리스트의 차이 대해서 알아봅니다. 배열과의 차이점 1. 메모리 차이 배열은 순차적인 데이터, 즉 메모리 영역이 연속적으로 사용됩니다. 연결리스트는 각 데이터가 퍼져있습니다. 즉, 포인터를 사용하여 각 영역을 참조합니다. 2. 요소의 삭제 / 추가 배열은 O(n) 시간이 소요됩니다. 연결리스트의 삭제와 추가는 O(1) 시간이 소요됩니다. 연결 리스트의 특징 연결 리스트는 인덱스가 없습니다. 연결 리스트는 무작위 접근이 불가능합니다. 연결 리.. 이전 1 다음
