[미련을 못버린] 힙. 힙소트

땡칠도사

2012.05.05 13:29:24

조회 112 추천 0 댓글 2

(1) 일단 힙소트

function HeapSort ( data[], ref result[] )

Heap H = new Heap

foreach element e in data

H.push (e)

endfor

while (H not empty)

result.append (H.pop())

endwhile

endfunction

(2) 그리고 힙

힙은 이진트리 기반 자료구조로서, 다음과 같은 성질을 가진다.

[성질 1] 최상위 노드(루트)는 언제나 힙에서 우선순위가 가장 높은 항목이다.

[성질 2] 부모노드는 언제나 자식보다 높은 우선순위를 가짐

(* 삽입/제거시를 제외한 어떠한 상황에서도 위의 성질은 반드시 지켜져야함.)

솔직히 이 녀석 자체에는 큰 의미는 없고, 그냥 그렇다는 거임 ㅇㅇ

단지 이런 성질을 가진 녀석이 유용하니까 이름이 붙고 교과서에 나오는거임.

(*) 아까 글에서 설명을 안한부분

아마 아까 여기서 햇갈려한 모양인것 같은데,

힙은 어디까지나 이진트리. 배열을 쓰는건 단순히 편의를 위한거임.

노드 H[n]가 있을 때 이놈의 자식은 H[2n], H[2n+1]이 되는 식임

그러니까 배열 자체가 정렬되어있을 리는 없지.

힙소트가 push후에 pop을 하는 이유가 이거임 - _-)

고정닉 0

원본 첨부파일 1

dc_kowa.png

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	연말 모임 가는 곳마다 가장 인싸일 것 같은 스타는?	운영자	25/12/08	-	-
AD	AI 가전 디지털 모음전	운영자	25/11/27	-	-
공지	프로그래밍 갤러리 이용 안내 [98]	운영자	20.09.28	48880	65
2907743	"중·러 폭격기 도쿄 방향으로 날아‥이례적"	발명도둑잡기(39.7)	12:53	2	0
2907742	윤석열이 열어젖힌 '오버턴 창'	발명도둑잡기(118.216)	12:49	2	0
2907741	지금까지 이런 기업은 없었다…남다른 ‘김범석의 쿠팡’	발명도둑잡기(118.216)	12:43	3	0
2907740	이스라엘이 키운 가짜 영웅, 내부 총질 와중에 횡사하다	발명도둑잡기(118.216)	12:37	10	0
2907739	트럼프·빌 게이츠·클린턴까지... 미 민주당, 엡스타인 사진 공개	발명도둑잡기(118.216)	12:27	6	0
2907738	한학자 "민주당 축복 못하겠다"…'양쪽 어프로치' 통일교 변심 왜	발명도둑잡기(118.216)	12:23	6	0
2907737	내란세력 윤어게인의 나라는 망해도 됩니다	발명도둑잡기(118.216)	12:11	9	0
2907736	대학 컴공가기 vs 사범대가기 [1]	프갤러(223.38)	11:58	15	0
2907735	하찮아보이는 선배가 우스워 보이더라도 [11]	chironpractor	08:25	82	0
2907734	인지과학조져라	손발이시립디다	07:56	32	0
2907733	이미지 [단독] 선행매매로 112억 번 기자, 이투데이-서울경제-서울경제	ㅇㅇ(211.36)	07:34	22	0
2907732	해 낚시 ㅇㅅㅇ [1]	헤르 미온느	07:32	26	0
2907731	태연 ㅇㅅㅇ [1]	헤르 미온느	07:28	23	0
2907730	하루 한 번 헤르미온느 찬양 [1]	헤르 미온느	07:27	40	0
2907729	씨발년들아. 그래서 얼마나 많이 다중이 만들어써?	프갤러(202.9)	07:14	29	0
2907728	삼성에 프로그래머로 취직 햇는데 하루 12시간. MP4 [1]	마인츠05	06:38	93	0
2907727	OctoX is a radical Rust implementation	발명도둑잡기(118.216)	05:22	20	0
2907725	컴공 학부 4년 과정 독학하는데 얼마나 걸림? [3]	멍멍이(222.110)	02:23	83	0
2907724	고수가 되고 싶습니다 [1]	멍멍이(222.110)	02:21	45	0
2907723	이 정도면 어느 정도 수준인거임? 네카라쿠배 가냐 [3]	프갤러(115.91)	02:10	76	0
2907721	db 공부하다가	프갤러(210.94)	02:07	36	0
2907720	다당제 선거제도로 개혁 못하면 국민의힘이 정권교체 했을때 피해가 크다	발명도둑잡기(118.216)	01:38	29	0
2907718	베네수엘라 공격...마약 단속 아니라 석유 장악이 목적?	발명도둑잡기(118.216)	01:17	26	0
2907717	마동석은 되고 유승준은 안되는 진짜 이유	발명도둑잡기(118.216)	01:10	29	0
2907716	고슴도치케루빔이 666짐승 엘리베이터에 탑승한 테마음악	책사풍후zen	01:05	29	0
2907715	게임핵 방지프로그램, 바이러스 백신, DRM 등은 모두 빅브라더 기술이다	발명도둑잡기(118.216)	00:50	57	1
2907713	권도형 15년형 테라=포트녹스 금=달러=지니어스법=테더=써클 [2]	발명도둑잡기(118.216)	00:23	40	0
2907711	컴퓨터공학이 배우는게 뭐임? [4]	프갤러(106.241)	12.12	91	0
2907710	카메라 시장을 장악한 중국	발명도둑잡기(118.216)	12.12	37	0
2907709	이재명씨에게 개털리는 아저씨봐라 [1]	헬마스터	12.12	59	0
2907707	12월 러스트 순위 feat. 티오베 [3]	나르시	12.12	66	0
2907706	한국 여성 자살률, 남성보다 낮다?…"고위험군은 약 2배"	발명도둑잡기(118.216)	12.12	33	0
2907704	아이유 2025 AAA	발명도둑잡기(118.216)	12.12	26	0
2907703	동일본 대지진 성금	발명도둑잡기(118.216)	12.12	24	0
2907702	[슈퍼걸]1차 예고편	발명도둑잡기(118.216)	12.12	22	0
2907700	만4년차 연협 고민중이다	프갤러(118.235)	12.12	27	0
2907699	아랫집 청년이 층간소음으로 올라와서 목 조인 거 맞다니까요... [1]	넥도리아(119.195)	12.12	47	0
2907698	계엄 후 1년…반토막 난 성장률, 급등한 환율	발명도둑잡기(118.216)	12.12	21	0
2907697	그러고 보니 유튜브나 SNS, 커뮤도 블록체인과 닮은 면이 있네	chironpractor	12.12	25	0
2907696	광주도서관 붕괴됐대서 생각나는 예전 글	발명도둑잡기(118.216)	12.12	29	0
2907695	web3 개발자 있냐 백억대 프로젝트 할사람 [1]	프갤러(106.101)	12.12	59	0
2907694	국가보안법이 역사교과서를 왜곡한 결과 [5]	발명도둑잡기(118.216)	12.12	44	0
2907693	이준호 가고 박신혜 왔다…베일 벗으며 강렬한 첫인상 남긴 韓 드라마	발명도둑잡기(118.216)	12.12	40	0
2907692	틀딱 문과충들이 원래 한글에 집착함 [3]	헬마스터	12.12	44	0
2907691	[단독] 선행매매로 112억 번 기자, 이투데이-서울경제-서울경제TV 거	발명도둑잡기(118.216)	12.12	24	0
2907689	이게 대통령이 직접 지시해야 할 일이냐? [7]	chironpractor	12.12	66	1
2907687	백악관, 중일갈등 '중립기어'…"트럼프, 양국정상과 좋은관계"	발명도둑잡기(118.216)	12.12	23	0
2907686	싱글벙글 포괄임금제 드디어 폐지 직전	발명도둑잡기(118.216)	12.12	29	0
2907685	익명 인터넷 Tor 프로그램 C에서 메모리 안전 언어 Rust로 전환	발명도둑잡기(118.216)	12.12	45	0