기본 콘텐츠로 건너뛰기

[DATA STRUCTURE] HEAP

What is Binary Heap?
Let us first define a Complete Binary Tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible (Source Wikipedia)

Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.

Why array based representation for Binary Heap?
Since a Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient. If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and right child by 2 * I + 2 (assuming the indexing starts at 0).

public class HeapSort {

    void sort(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1i >= 0i--) {
            System.out.println(i);
            maxHeapify(arrni);
        }
        // One by one extract an element from heap
        for (int i = n - 1i > 0i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            maxHeapify(arri0);
        }

    }

    private void maxHeapify(int[] arrint nint i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;

        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;

        }
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            maxHeapify(arrnlargest);
        }

    }

    private void smallHeapify(int[] arrint nint i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] < arr[smallest]) {
            smallest = left;
        }
        if (right < n && arr[right] < arr[smallest]) {
            smallest = right;
        }
        if (smallest != i) {
            int swap = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = swap;

            smallHeapify(arrnsmallest);
        }
    }

    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0i < ni++) {
            System.out.println(arr[i] + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int arr[] = { 121113567 };
        int n = arr.length;

        HeapSort h = new HeapSort();
        h.sort(arr);
        System.out.println("Sorted array is");
        printArray(arr);
    }

}


REFERENCE

https://www.geeksforgeeks.org/heap-sort/

댓글

이 블로그의 인기 게시물

기본적인 MongoDB 사용/자바연동

mongoDB 명령어 db: 현재 사용 중인 데이터베이스 확인 -test :Default로 들어가 있는 test 테이블 show dbs : DB의 리스트 확인 show collections : collection 리스트 확인, collection = table in mongoDB show tables : 위 명령어와 같음 db.stats() : 데이터베이스 상태 확인 db.(db명).drop(): 안에 있는 데이터 삭제 mongod --version => mongodb 확인 mongo -version => shell 확인 use 테이블 명: 테이블 생성 db.dropDatabase() : 접속된 테이블 삭제 -테이블 확인 필요!! db.createCollection(“테이블 명”): 테이블 생성 db.테이블 명.drop(): 테이블 지움 db.blog[테이블 명].insert({“name ” : “ nodejs”}) : 내용(Document)을 추가 db.테이블 명.insert([ {“ ” : “ ”},{“ ” : “ ”}]); -여러 Documents를 하나의 테이블에 넣는 방법 db.blog[테이블 명].find() : 내용 확인 db.테이블 명.find().pretty() : 보기 좋게 검색 id : primary key를 자동으로 부여해줌 db.테이블 명.remove({“name” : “book01”}) : 특정한 Documents를 지우는 법 insert 문 count 문 연산자 몽고디비 비교 연산자 $eq 2. $gt 3. $gte 4. $lt 5. $lte ne : 주어진 값과 일치 하지 않는 값 in: 주어진 배열 안에 속하는 값 nin: 주어진 배열 안에 속하지 않는 값 몽고디비 논리연산자 1.$or: 주어진 조건 중 하나라도 tr...

Twelve-Factor 마이크로서비스 서비스 애플리케이션 구축

Practice DevOps! • 코드베이스(codebase): 모든 애플리케이션 코드와 서버 프로비저닝(provisioning) 정보는 버전 관 리(version control)되어야 한다. 각 마이크로서비스는 소스 제어 시스템 안에 독립적인 코드 저장소 를 가져야 한다. • 의존성(dependencies): 애플리케이션이 사용하는 의존성을 메이븐(자바) 같은 빌드 도구를 이용해 명시적으로 선언해야 한다. 제3자(3 rd party)의 JAR 의존성은 특정 버전 번호를 붙여 명시해 선언해 야 한다. 따라서 동일 버전의 라이브러리를 사용해 항상 마이크로서비스를 빌드할 수 있다. • 구성(config): 애플리케이션 구성(특히 환경별 구성)을 코드와 독립적으로 저장하자. 애플리케이션 구성은 절대로 소스 코드와 동일한 저장소에 있으면 안 된다. • 백엔드 서비스(backing services): 마이크로서비스는 대개 네트워크를 거쳐 데이터베이스나 메시징 서비스와 통신한다. 그렇다면 언제든 데이터베이스 구현을 자체 관리형 서비스에서 외부업체 서비스 로 교체할 수 있어야 한다. 10장에서 로컬에서 관리되는 Postgres 데이터베이스를 AWS 데이터베 이스로 옮기면서 이를 보여 준다.  • 빌드, 릴리스, 실행(build, release, run): 배포할 애플리케이션의 빌드, 릴리스, 실행 부분을 철저히 분리하라. 코드가 빌드되면 개발자는 실행 중에 코드를 변경할 수 없다. 모든 변경 사항을 빌드 프로 세스로 되돌려 재배포해야 한다. 빌드된 서비스는 불변적이므로(immutable) 변경할 수 없다. • 프로세스(processes): 마이크로서비스는 항상 무상태(stateless) 방식을 사용해야 한다. 서비스 인 스턴스 손실에 의해 데이터가 손실될 것이라는 우려 없이 언제든 서비스를 강제 종료하거나 교체할 수 있다. • 포트 바인딩(port binding): 마이크로서비스는 서비스용 런타임 엔진을 포함한(실행 파일에 패키징 된 서비...

[AWS] Kinesis 개념 정리

What is STREAM DATA가 모이는 흐르는 곳 Stream 에 모이는 데이터는 유니크한 Partition Key 로 각 Shard 에 분산됨. (Shard수에 의해 분산되는 Shard가 달라짐) What is Shard 샤드 는 스트림에서 고유하게 식별되는 데이터 레코드 시퀀스입니다. 스트림은 하나 이상의 샤드로 구성되며 각 샤드는 고정된 용량 단위를 제공합니다. 각 샤드는 최대 읽기: 5개의 초당 트랜잭션, 최대 총 데이터 읽기 속도: 초당 2MB 및 최대 쓰기: 1,000개의 초당 레코드, 최대 총 데이터 쓰기 속도: 초당 1MB(파티션 키 포함)를 지원할 수 있습니다. 스트림의 데이터 용량은 스트림에 지정하는 샤드 수의 함수입니다. 스트림의 총 용량은 해당 샤드의 용량의 합계입니다. 데이터 속도가 증가하면 스트림에 할당된 샤드 수를 늘리거나 줄일 수 있습니다. 자세한 내용은  스트림 리샤딩  단원을 참조하십시오. Stream 에 모여있는 데이터를 컨슈머(데이터를 사용하는 서버) 전달하는 입구 Stream 을 작성할 때 샤드 수를 설정가능( 샤드 수가 많을 수록 비용이 비싸짐) Stream 내부에 데이터를 취득하기 위한 샤드 가 미리 정해져있음 ( Stream 에 데이터를 등록한 시점에 그 데이터를 어느 샤드 에 취득 가능하는지 구별됨) What is Partition Key 파티션 키는 스트림 내에서 샤드별로 데이터를 그룹화하는 데 사용 Kinesis Data Streams는 스트림에 속한 데이터 레코드를 여러 샤드로 분리 각 데이터 레코드와 연결된 파티션 키를 사용하여 해당 데이터 레코드가 속한 샤드를 확인 최대 길이 제한이 256자인 유니코드 문자열,파티션 키를 128비트 정수 값에 매핑하고 샤드의 해시 키 범위를 사용하여 연결된 데이터 레코드를 샤드에 매핑하기 위해 MD5 해시 함수가 사용 데이터 분활 룰 파티션 키: 최대 256바이트 unicode문자열 ->Hashing 128 정수로 매핑(해시 키) -> H...