우선순위 큐

wellsbabo·2023년 4월 7일
0

자료구조

목록 보기
6/7
post-thumbnail

우선순위 큐

개요

  • 우선순위가 높은 데이터가 먼저나옴. FIFO가 아님
  • 우선 순위가 같은 경우는 FIFO

enqueue, dequeue

  • 우선순위 큐를 힙으로 구성하면, 최소 힙 및 최대 힙의 삽입 삭제와 같음

구현

1) 배열
2) 연결리스트
- 추가할 때 링크로 끼워넣으면 되지만, 전체와 하나하나 비교해야하는 상황도 생기기때문에 enqueue가 O(N)을 가진다
3) 힙
- 자바 내부적으로는 우선순위 큐를 힙으로 구현했음


소스코드

기본 구현

// 연결 리스트를 이용한 우선순위 큐
// 자바 기본 PriorityQueue

import java.util.*;

public class Main {
    //우선순위 큐(낮은 숫자 순)
    public static void enqueue(LinkedList<Integer> list, int data) {
        int idx = list.size();  //집어넣을 맨 마지막 인덱스
        for (int i = 0; i < list.size(); i++) { //우선순위 큐(리스트)를 돌면서
            if(list.get(i) > data){ //data보다 큰수(우선순위가 낮은 수)를 만나면 그 인덱스를 가져옴
                idx = i;
                break;
            }
        }
        list.add(idx, data);    //위에 인덱스에다가 data 삽입
    }

    public static Integer dequeue(LinkedList<Integer> list) {
        if(list.size() == 0 ){
            return null;
        }
        int data = list.get(0);
        list.remove(0); //가장 첫번째 수 제거
        return data;    //반환
    }

    public static void main(String[] args) {
        // 연결리스트를 이용한 우선순위 큐
        System.out.println("== 연결리스트 방식의 우선순위 큐 ==");
        LinkedList<Integer> pqList = new LinkedList();
        enqueue(pqList, 5);
        enqueue(pqList, 7);
        enqueue(pqList, 3);
        enqueue(pqList, 1);
        enqueue(pqList, 9);
        System.out.println(pqList);

        System.out.println(dequeue(pqList));
        System.out.println(dequeue(pqList));
        System.out.println(pqList);
        System.out.println();

        // 자바 기본 PriorityQueue 사용
        System.out.println("== 자바 기본 우선순위 큐 ==");
        // 우선순위: 낮은 숫자 순
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(5);
        pq.add(7);
        pq.add(3);
        pq.add(1);
        pq.add(9);
        System.out.println(Arrays.toString(pq.toArray()));

        // 우선순위: 높은 숫자 순
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
        pq2.add(5);
        pq2.add(7);
        pq2.add(3);
        pq2.add(1);
        pq2.add(9);
        System.out.println(Arrays.toString(pq2.toArray()));

    }
}

멤버 변수가 여러개 일때 비교

// 나이 순으로 오름차순 또는 내림차순 출력

import java.util.Arrays;
import java.util.PriorityQueue;

class Person implements Comparable<Person>{
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person o) {
        //1: 변경 안함
        //-1: 변경

        //this.age가 추가하는 데이터
        //추가하는 데이터가 더 작을 때 변경(작은 값이 위로 올라감, 오름차순)
//        return this.age >= o.age? 1 : -1;
        return this.name.compareTo(o.name);
        //새롭게 추가하는 데이터가 더 클 때 변경(큰 값이 위로 올라감, 내림차순)
        //return this.age <= o.age? 1: -1;

    }
}

public class Practice1 {
    public static void solution(String[] name, int[] age) {
        PriorityQueue<Person> pq = new PriorityQueue<>();

        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person(name[i], age[i]));
        }
        System.out.println("== 내부 힙 구조 ==");    //내부구조는 꼭 우선순위대로 이루어져있지는 않다
        pq.stream().forEach(x -> System.out.println(x.name + " " + x.age));
        System.out.println();
        System.out.println("== 실제 출력 순서 ==");
        while(!pq.isEmpty()){
            Person p = pq.poll();   //우선순위대로 뽑아낸다
            System.out.println(p.name + " " + p.age);
        }
    }

    public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age);

        //람다를 이용한 비교 방식
        System.out.println();
        //p1이 추가되는 데이터
        PriorityQueue<Person> pq2 = new PriorityQueue<>((Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);

        for (int i = 0; i < name.length; i++) {
            pq2.offer(new Person(name[i], age[i]));
        }

        while(!pq2.isEmpty()){
            Person p = pq2.poll();
            System.out.println(p.name + " " + p.age);
        }
    }
}

멤버 변수 중 문자로 비교

// 문자열 사전식 오름차순

import java.util.PriorityQueue;

class Person2 {
    String name;
    int age;

    public Person2(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

public class Practice2 {
    public static void solution(String[] name, int[] age) {
        PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name));    //문자열 오름차순
//        PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p2.name.compareTo(p1.name));    //문자열 내림차순
        //참고용
        //A가 더 작기때문에 -1이 나온다
        System.out.println("A".compareTo("B"));

        for (int i = 0; i < name.length; i++) {
            pq.offer(new Person2(name[i],age[i]));
        }

        while(!pq.isEmpty()){
            Person2 p = pq.poll();
            System.out.println(p.name + " " + p.age);
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name));

        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age);
    }
}

0개의 댓글