Hashmap, Tree(BFS,DFS, 탐색), Heap

hashmap

import java.util.HashMap;

public class HashTest {
    public static void main(String[] args){
        HashMap<String, Integer> hashMap = new HashMap<>();

        hashMap.put("abc", 3);
        hashMap.put("def", 4);
        hashMap.put("xyz", 5);
        hashMap.put("abc", 6);

        for (String key : hashMap.keySet()) { // return Set
            System.out.println(key + " : " + hashMap.get(key));
        }
        for (Integer value : hashMap.values()) { // return Collections
            System.out.println(value);
        }

    }
}

#메소드

1) 데이터 추가

- V put(K key, V value) : key, value를 저장
- void putAll(Map<? extends K, ? extends V> m) : Map m의 데이터를 전부 저장
- V putIfAbsent(K key, V value) : 기존 데이터에 key가 없으면  key와 value를 저장

2) 데이터 삭제

- void clear( ) : 모든 데이터를 삭제
- V remove(Object key) : key와 일치하는 기존 데이터(key, value)를 삭제
- boolean remove(Object key, Object value) : key와 value가 동시에 일치하는 데이터를 삭제

3) 데이터 수정

- V replace(K key, V value) : key와 일치하는 기존 데이터의 value를 변경 
- V replace(K key, V oldValue, V newValue) : key와 oldValue가 동시에 일치하는 데이터의 value를 newValue로 변경

4) 데이터 확인

- boolean containsKey(Object key) : key와 일치하는 데이터가 있는지 여부를 반환 (있으면 true)
- boolean containsValue(Object value) : value가 일치하는 데이터가 있는지 여부를 반환 (있으면 true)
- boolean isEmpty( ) : 데이터가 빈 상태인지 여부를 반환 (빈 상태면 true)
- int size( ) : key-value 맵핑 데이터의 개수 

5) 데이터 반환

- V get(Object key) : key와 맵핑된 value값을 반환 
- V getOrDefault(Object key, V defaultValue) : key와 맵핑된 value값을 반환하고 없으면 defaultValue값을 반환
- Set<Map.Entry<K, V>> entrySet( ) : 모든 key-value 맵핑 데이터를 가진 Set 데이터를 반환 
- Set<K> keySet( ) : 모든 key 값을 가진 Set 데이터를 반환 
- Collection<V> values( ) : 모든 value 값을 가진 Collection 데이터를 반환

Tree

BFS

큐 반복 - offer-poll 사용; push-pop는 스택 버전(LIFO)이기에 안 됨

static void bfs(int idx){
    ArrayDeque<Integer> q = new ArrayDeque<>();
    q.offer(idx);

    while(!q.isEmpty()){
        int cur = q.poll();
        sb.append(tree[cur]).append("->");

        int lc = cur*2;
        int rc = cur*2 + 1;

        if(lc< tree.length) q.offer(lc);
        if(rc< tree.length) q.offer(rc);
    }
}

DFS

재귀

static void dfs(int idx){
    if(idx >= tree.length) return;

    sb.append(tree[idx]).append("->");

    dfs(idx*2);
    dfs(idx*2+1);
}

전위(preOreder), 중위(inOreder), 후위(postOreder)

전위+중위
=>
전위는 root가 먼저 나오기에
먼저 나오는 값을 root로 두고 좌우로 나눈다.
좌우로 나눈 거에서 또 제일 먼저 나오는 것을 root로 둬서 좌우로 나눈다.
null이 될 때까지, 반복을 하면, 원래 트리를 구현할 수 있다.

중위+후위는 반대로 제일 뒤에가 root다.
제일 뒤에 오는 값

Heap

완전 이진 트리의 일종, 우선순위 큐를 위해 만들어진 구조
BST는 전체 순서를 보장하지만, Heap은 부모-자식 간만의 크기 보장이 된다
=> 탐색은 힘들지만 최대, 최소 찾는데는 O(1)이다
=> 우선순위 큐, 스케줄링, k번째 최대/최소가 필요할때 사용한다