일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- SpringBoot
- AOP
- 그리디
- http
- 알고리즘
- JPQL
- spring
- jpa
- 스프링 핵심 기능
- Greedy
- Spring Boot
- Thymeleaf
- Android
- 스프링 핵심 원리
- 인프런
- Servlet
- springdatajpa
- java
- JDBC
- Proxy
- 백준
- db
- 김영한
- pointcut
- kotlin
- transaction
- 자바
- QueryDSL
- Exception
- 스프링
- Today
- Total
목록HeapSort (2)
개발자되기 프로젝트
1. Element 삭제하기 루트에 있는 값(별)은, min heap일 때 제일 작고, max heap일 경우 가장 크다. 즉 heap에서 꺼낼 경우 루트에 있는 요소만 꺼낸다. 2. 10을 꺼냈다. 빈칸으로 남는다. 3. 빈칸에는 가장 마지막에 있는 요소가 들어온다고 가정하자. 4. 이 때, 80이 저 위치에 있는게 맞냐?! min heap인 경우 child 중 가장 작은 수와 비교하고. max heap인 경우 child중 가장 큰 수와 비교한다. 지금은 min heap이니 80과 20을 비교한다. 5. 80은 20보다 크다. 80이 기존 20의 자리에 있다고 가정하자! 6. child 중 가장 작은 수인 40과 비교하자. 7. 80은 40보다 크다. 80이 기존 40의 위치에 있다고 가정하자! 8. ..
평균 수행시간이 O(logN)인 경우 : 한 번 수행할 때 마다 정렬해야 하는 수가 1/2개로 줄어드는 경우 - Quick 정렬(퀵 정렬) : worst인 경우 O(n^2) 까지 가능.. - Merge 정렬(병합 정렬) : 메모리를 가지고 있다. element를 분배한다. 얘네를 다시 병합하면서 sorting - Heap 정렬(힙 정렬) : Heap 이라는 tree구조. 실제 구현은 배열로 만듦. 단, Merge 정렬과 Heap 정렬은 추가적인 메모리가 필요하다. 0. Heap 정렬 Heap 이란? complite binary tree(BT)를 의미한다. Complite Binary Tree란? 이진 트리로, 1) 무조건 element가 왼쪽부터 채워져야 하고 2) height가 h라 할 때, h-1까지..