Python으로 구현하는 자료구조 : Heap

Python으로 Heap을 구현해보고 Heap 자료구조의 특징과 데이터의 삽입과 삭제에 대해 알아보도록 하겠습니다. # Heap이란 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조입니다. 힙에는 두가지 종류가 있으며, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 부릅니다. 원소 값의 대소 관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않습니다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리 노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적..
Data structure 2019. 5. 11. 09:00

Python으로 구현하는 자료구조 : Linked List (3) Circular linked list

이 포스팅에서는 Circular linked list의 특징을 알아보고 파이썬으로 Circular linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Circular linked list란 환형 연결 리스트라고도 부르는 이 연결 리스트는 머리와 꼬리가 연결되어 순환 구조를 지닙니다. 환형 연결 리스트라는 것은 Node에 포인터 공간이 두 개 일수도 있고, 한개 일수도 있으며 포인터 공간의 개수가 중요한 것이 아니라 노드의 Next가 None인 경우가 없이 끊임 없이 이어진다는 의미입니다. 따라서 노드가 한개인 경우에도 무한대로 순환할 수 있습니다. # Circular linked list 구현하기 # 삽입 # 삭제 # 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
Data structure 2019. 5. 10. 09:30

Python으로 구현하는 자료구조 : Linked List (2) Doubly linked list

이 포스팅에서는 Doubly linked list의 특징을 알아보고 파이썬으로 Doubly linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Doubly linked list 란? Doubly linked list는 각 노드에 자료 공간과 두 개의 포인터 공간이 있고, 각 노드의 포인터는 이전 노드와 다음 노드를 가리킵니다. # 이중 연결 리스트의 특징, 장점, 단점은요 단순 연결리스트와 이중 연결 리스트의 차이는 prev를 가리키는 포인터 공간이 추가되면서 이전 노드에 대한 정보를 알 수 있다는 점입니다. 이로인해 단순 연결 리스트로는 할 수 없는 역으로 출력하는 것이 가능하고, 특정 노드의 이전 노드를 삭제하거나 특정 노드의 이전에 삽입하는게 가능해졌습니다. 그러나 단순 연결 ..
Data structure 2019. 5. 9. 19:00