더미 기반 기본 작업 소개

1052 단어 c + +퇴적 작업
우리 가 기대 하 는 데이터 구 조 는 삽입 작업 을 지원 하고 그 중에서 최소 또는 최대 관건 코드 를 가 진 기록 을 편리 하 게 꺼 낼 수 있 습 니 다.이러한 데이터 구 조 는 우선 순위 대기 열 입 니 다.우선 순위 대기 열의 각종 실현 중에서 더 미 는 가장 효율 적 인 데이터 구조 이다.최소 더미:모든 노드 의 키 코드 는 좌우 자녀의 키 코드 보다 작 거나 같 습 니 다.더미 꼭대기 에 있 는 노드 의 키 코드 는 전체 요소 집합 이 가장 작 기 때문에 최소 더미 라 고 부 릅 니 다.가장 많은 유사 한 정의.
더미 만 들 기:아래 에서 위로 쌓 아 올 리 는 방법 으로 더 미 를 만 듭 니 다.아래 지점 에 하향 조정 알고리즘 sift Down 을 호출 하여 뿌리 로 하 는 하위 트 리 를 최소 로 조정 합 니 다.부분 에서 전체 로 최소 더 미 를 점차 확대 하여 전체 나 무 를 최소 더 미 를 조정 할 때 까지 한다.
하나의 요 소 를 삽입 합 니 다:최소 더미 의 삽입 알고리즘 은 다른 쌓 인 조정 방법 인 siftUp 을 호출 하여 아래 에서 위로 미 끄 러 지 는 조정 을 실현 합 니 다.매번 새로운 노드 는 이미 건 설 된 최소 더미 뒤에 꽂 혀 있 기 때문에 이 때 는 sift 와 반대 되 는 비교 경 로 를 지 키 고 아래 에서 위로,부모 노드 의 핵심 코드 와 비교 하여 조정 해 야 합 니 다.
하나의 요 소 를 삭제 합 니 다.최소 키 코드 기록 이 있 는 작업 을 삭제 할 때 최소 로 쌓 인 꼭대기 요 소 를 삭제 합 니 다.즉,완전 이 진 트 리 의 순서 로 표 시 된 0 번 요 소 를 삭제 합 니 다.이 요 소 를 가 져 간 후에 보통 마지막 노드 로 가 져 간 꼭대기 요 소 를 채 웁 니 다.그리고 쌓 인 실제 요소 의 개 수 를 1.줄 이지 만 마지막 요소 로 쌓 인 요 소 를 대체 하면 더 미 를 파괴 할 것 입 니 다.sift Down 알고리즘 을 사용 하여 더 미 를 조정 해 야 합 니 다.
본 논문 의 코드 는 모두 최소 더미 의 실현 을 예 로 들 수 있다.4567913)

좋은 웹페이지 즐겨찾기