LintCode 퇴적

1500 단어
정수 배열 을 보 여 주 는 것 은 그것 을 최소 배열 로 만 드 는 것 이다.배열 A 에 대해 A [0] 는 쌓 인 뿌리 이 고 모든 A [i] 에 대해 A [i * 2 + 1] 는 A [i] 의 왼쪽 아들 이 며 A [i * 2 + 2] 는 A [i] 의 오른쪽 아들 이다.더미 가 무엇 인지 설명 합 니까?더 미 는 데이터 구조 로 보통 세 가지 방법 이 있 습 니 다. push, pop, top.그 중에서 "push" 는 새로운 요 소 를 추가 하여 더미 에 들 어가 고 "pop" 은 더미 의 최소 / 최대 요 소 를 삭제 하 며 "top" 은 더미 의 최소 / 최대 요 소 를 되 돌려 줍 니 다.퇴적 이란 무엇 인가?무질서 한 정수 배열 을 하나의 배열 로 바꾸다.만약 에 가장 작은 더미 라면 모든 요소 A [i], 우 리 는 A [i * 2 + 1] > = A [i] 와 A [i * 2 + 2] > = A [i] 가 여러 가지 쌓 인 결 과 를 얻 을 수 있 습 니까?그 중 어느 것 도 되 돌려 줍 니 다.예 를 들 어 [3, 2, 1, 4, 5] 를 제시 하고 [1, 2, 3, 4, 5] 또는 그 어떠한 합 법 적 인 배열 도 되 돌려 줍 니 다.
코드
public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftdown(int[] A, int k) {
        while (k < A.length) {
            int smallest = k;
            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
                smallest = k * 2 + 1;
            }
            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
                smallest = k * 2 + 2;
            }
            if (smallest == k) {
                break;
            }
            int temp = A[smallest];
            A[smallest] = A[k];
            A[k] = temp;
            
            k = smallest;
        }
    }
    
    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
            siftdown(A, i);
        } 
    }
}
버클: 삽입 위치 검색
210731 TIL

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage