[JAVA] 힙정렬 구현하기

힙정렬 : 힙 트리구조를 이용한 정렬알고리즘

힙정렬을 알기 위해서 이진 트리를 알아야한다. 그 중 완전 이진트리에 대해 알아보자

완전 이진 트리
한개의 노드(RootNode)로 시작하여 새로운 노드가 들어오면 해당 노드의 왼쪽과 오른쪽 충 2개가 연결될 때 까지 연결
2개가 모두 연결되면 이미 연결된 자식노드 중에서 왼쪽노드의 왼쪽자리부터 차례대로 연결
이렇게 완성된 노드들을 완전 이진 트리 라고한다

힙정렬은 이 완전 이진 트리에서 최대값과 최소값을 빠르게 찾기위해 이용하는 정렬

최대 힙 : 부모 노드가 자식노드보다 큰 노드
힙정렬은 최대힙이 가장 위에서 부터 내려오는 정렬
하지만 최대힙이 성립되지 않아 힙구조가 무너지는 경우 성립되지 않은 부모노드를 가장 큰 자식노드와 교체한다

작성순서
1. 사용할 노드를 정의한다

class HeapNode {
    private final int value;
    private HeapNode parent;
    private HeapNode leftNode;
    private HeapNode rightNode;

    public HeapNode(int value) {
        this.value = value;
        leftNode = null;
        rightNode = null;
        parent = null;
    }

    public boolean isLeftChild() {
        return leftNode == null;
    }

    public boolean isRightChild() {
        return rightNode == null;
    }

    public int getValue() {
        return value;
    }

    public boolean setLeftNode(HeapNode node) {
        if (isLeftChild()) {
            leftNode = node;
            leftNode.parent = this;
            return true;
        }
        return false;
    }

    public boolean setRightNode(HeapNode node) {
        if (isRightChild()) {
            rightNode = node;
            rightNode.parent = this;
            return true;
        }
        return false;
    }

    public HeapNode getLeftNode() {
        return leftNode;
    }

    public HeapNode getRightNode() {
        return rightNode;
    }

    public HeapNode getParent() {
        return parent;
    }

    public void setParent(HeapNode node) {
        parent = node;
    }
}

2. 정의한 노드를 통해 이진트리구조를 만든다 

public void insertNode(HeapNode node) {
        if (rootIsEmpty()) {
            root = node;
            last = node;
            return;
        }

        Queue<HeapNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            HeapNode current = queue.poll();

            if (current.getLeftNode() == null) {
                current.setLeftNode(node);
                last = node;
                return;
            } else {
                queue.offer(current.getLeftNode());
            }

            if (current.getRightNode() == null) {
                current.setRightNode(node);
                last = node;
                return;
            } else {
                queue.offer(current.getRightNode());
            }
        }
    }

3. 이진트리 구조를 최대힙구조를 충족할 수 있게 한다 heapify 알고리즘 수행

private void buildMaxHeap(HeapNode current) {
        if (current == null) {
            return;
        }
        buildMaxHeap(current.getLeftNode());
        buildMaxHeap(current.getRightNode());
        maxHeapify(current);
    }

    private void maxHeapify(HeapNode current) {
        HeapNode largest = current;
        HeapNode left = current.getLeftNode();
        HeapNode right = current.getRightNode();
        if (left != null && left.getValue() > largest.getValue()) {
            largest = left;
        }
        if (right != null && right.getValue() > largest.getValue()) {
            largest = right;
        }
        if (largest != current) {
            swap(current, largest);
            maxHeapify(largest);
        }
    }

4. 정렬을 한다 ( root를 제일 끝단의 노드와 바꾸고 그 노드를 제외하고 heapify알고리즘 수행)

public void sort(int[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(root, last);
            arr[i] = last.getValue();
            moveLastHeap();
            buildMaxHeap(root);
        }
    }
    
    public void moveLastHeap() {
        HeapNode lastToParent = last.getParent();
        if (lastToParent == null) return;
        if (lastToParent.getLeftNode() == last) {
            lastToParent.removeLeft();
        } else {
            lastToParent.removeRight();
        }
        last.setParent(null);
        index--;
        last = nodeList.get(index);
     }

전체코드(뭔가 너무 막쓴코딩 같아서 한번 수정해야겠다..)
수정필요한 내용
1. list를 통한 last노드를 찾는 방식을 빼고 관리하는 방법을 생각해보자
2. swap을 value교환이 아닌 객체교환으로 하는 방법을 생각해보

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        NodeManager nodeManager = new NodeManager();
        nodeManager.insertNode(new HeapNode(10));
        nodeManager.insertNode(new HeapNode(15));
        nodeManager.insertNode(new HeapNode(17));
        nodeManager.insertNode(new HeapNode(12));
        nodeManager.insertNode(new HeapNode(14));
        nodeManager.insertNode(new HeapNode(16));
        nodeManager.insertNode(new HeapNode(13));
        nodeManager.insertNode(new HeapNode(11));
        nodeManager.insertNode(new HeapNode(19));

        nodeManager.heapSort(9);

    }
}

class NodeManager {
    private final ArrayList<HeapNode> nodeList;
    private HeapNode root;
    private HeapNode last;
    private int index;

    public NodeManager() {
        root = null;
        last = null;
        index = 0;
        nodeList = new ArrayList<>();
    }

    public boolean rootIsEmpty() {
        return root == null;
    }

    public HeapNode getRoot() {
        return root;
    }

    public void insertNode(HeapNode node) {
        if (rootIsEmpty()) {
            root = node;
            nodeList.add(root);
            return;
        }

        Queue<HeapNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            HeapNode current = queue.poll();

            if (current.getLeftNode() == null) {
                current.setLeftNode(node);
                last = node;
                nodeList.add(last);
                index++;
                return;
            } else {
                queue.offer(current.getLeftNode());
            }

            if (current.getRightNode() == null) {
                current.setRightNode(node);
                last = node;
                nodeList.add(last);
                index++;
                return;
            } else {
                queue.offer(current.getRightNode());
            }
        }
    }

    public void heapSort(int arrSize) {
        buildMaxHeap(root);
        int[] arr = new int[arrSize];
        sort(arr);
        for (int i = 0; i < arrSize; i++) {
            System.out.println(arr[i]);
        }
    }

    public void sort(int[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(root, last);
            System.out.println("root " + root.getValue() + "last" + last.getValue());
            arr[i] = last.getValue();
            moveLastHeap();
            buildMaxHeap(root);
        }
    }

    public void moveLastHeap() {
        HeapNode lastToParent = last.getParent();
        if (lastToParent == null) return;
        if (lastToParent.getLeftNode() == last) {
            lastToParent.removeLeft();
        } else {
            lastToParent.removeRight();
        }
        last.setParent(null);
        index--;
        last = nodeList.get(index);
     }

    private void buildMaxHeap(HeapNode current) {
        if (current == null) {
            return;
        }
        buildMaxHeap(current.getLeftNode());
        buildMaxHeap(current.getRightNode());
        maxHeapify(current);
    }

    private void maxHeapify(HeapNode current) {
        HeapNode largest = current;
        HeapNode left = current.getLeftNode();
        HeapNode right = current.getRightNode();
        if (left != null && left.getValue() > largest.getValue()) {
            largest = left;
        }
        if (right != null && right.getValue() > largest.getValue()) {
            largest = right;
        }
        if (largest != current) {
            swap(current, largest);
            maxHeapify(largest);
        }
    }

    public void swap(HeapNode parent, HeapNode child) {
        if (parent == null || child == null) return;
        int temp = parent.getValue();
        parent.setValue(child.getValue());
        child.setValue(temp);
    }

}

class HeapNode {
    private int value;
    private HeapNode parent;
    private HeapNode leftNode;
    private HeapNode rightNode;

    public HeapNode(int value) {
        this.value = value;
        leftNode = null;
        rightNode = null;
        parent = null;
    }

    public boolean isLeftChild() {
        return leftNode == null;
    }


    public boolean isRightChild() {
        return rightNode == null;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public void removeLeft() {
        leftNode = null;
    }

    public void removeRight() {
        rightNode = null;
    }

    public boolean setLeftNode(HeapNode node) {
        if (isLeftChild()) {
            leftNode = node;
            leftNode.parent = this;
            return true;
        }
        return false;
    }

    public boolean setRightNode(HeapNode node) {
        if (isRightChild()) {
            rightNode = node;
            rightNode.parent = this;
            return true;
        }
        return false;
    }

    public HeapNode getLeftNode() {
        return leftNode;
    }

    public HeapNode getRightNode() {
        return rightNode;
    }

    public HeapNode getParent() {
        return parent;
    }

    public void setParent(HeapNode node) {
        parent = node;
    }
}