ให้นิสิตทำการปรับปรุงโปรแกรมที่ให้โดยเพิ่มความสามารถให้ตรงกับความต้องการของข้อกำหนด

โดยที่โปรแกรมที่จะให้นิสิตทำการปรับปรุงนี้จะเป็นโปรแรกม Binary Tree Heap ซึ่งเป็นโครงสร้างข้อมูลแบบ Binary Tree แต่มีความสามารถแบบ Heap นั้นคือ ข้อมูลจะมีการเรียงจากน้อยไปมาก หรือมากไปน้อยได้ (DataLeft < DataRight หรือ DataLeft > DataRight) แต่โครงสร้างของ Tree จะเป็น Complete Binary Tree เสมอ

ซึ่ง Binary Heap นี้จะเสมือนเป็น Priority Queue จะมีฟังก์ชัน enqueue ในการเพิ่มข้อมูลและ dequeue ในการนำข้อมูลออกจาก Priority Queue นี้ การเพิ่มข้อมูลจะต้องมีการเรียงความสำคัญของข้อมูลตามตัวแปร mode_max ซึ่งเป็นตัวแปรในการบอกว่าข้อมูลนี้จะเรียงจาก มากไปน้อย หรือ น้อยไปมาก นั้นคือถ้า mode_max เป็น True จะต้องแสดงข้อมูลจากมากไปน้อย และถ้าเป็น False จะแสดงข้อมูลจากน้อยไปมาก

หน้าที่ของนิสิตคือ

1.     ทำการปรับปรุงฟังก์ชัน in_order_traversal ซึ่งเป็นฟังก์ชันในการทำ Recursion สำหรับ in-order tree traversal โดยจะมีการเรียกใช้งานผ่านฟังก์ชัน show_in_order

2.     ทำการปรับปรุงฟังก์ชัน dequeue ให้ทำการนำข้อมูลที่มีค่าตาม mode_max นั้นคือ ถ้ามี mode_max เป็น True ให้นำค่ามากที่สุดออก ถ้าเป็น False ให้นำค่าน้อยสุดออก

3.     ทำการสร้างฟังก์ชัน sort_min_to_max ที่จะเรียงข้อมูลใน Tree ให้ตรงตามเงื่อนไขค่าน้อยไปมาก

4.     ทำการสร้างฟังก์ชัน sort_max_to_min ที่จะเรียงข้อมูลใน Tree ให้ตรงตามเงื่อนไขค่ามากไปน้อย



โดยข้อกำหนดมีดังนี้

1.     ข้อมูลตอนที่ใช้งานฟังก์ชัน show_in_order จะต้องแสดงข้อมูลที่เรียงตามตัวแปร mode_max

2.     ข้อมูลใน data ต้องเป็นรูปแบบของ Heap นั้นคือ

index ที่ 0 เป็น root

ค่า Left จะเป็น (2 * i) + 1

ค่า Right จะเป็น (2 * i) + 2

โดยที่ i คือตำแหน่งของข้อมูลที่เป็น Parent

3.     การเรียงข้อมูลในฟังก์ชัน sort_min_to_max และ sort_max_to_min ต้องไปเปลี่ยนตำแหน่งข้อมูลในตัวแปร data แต่ยังคงให้เป็นรูปแบบของ Heap



ตัวอย่างเช่น

ถ้าเพิ่มข้อมูลมาเป็น 1 5 3 4

ข้อมูลเวลาใช้ฟังก์ชัน show_in_order จะเป็น 1 3 4 5

โดยโครงสร้างของ Tree เวลาใช้ฟังก์ชัน show_tree จะได้เป็น

4

3 5

1

หรือถ้าใช้ show_array จะได้เป็น 4 3 5 1



*หมายเหตุ ส่วนที่ให้นิสิตทำการแก้ไขโปรแกรมนั้นจะมี Comment // TODO: บอกไว้อยู่ แต่อย่างไรก็ตามนิสิตสามารถแก้ไข หรือเพิ่มเติมฟังก์ชันอื่น ๆ ได้



-------------

Heap Class

-------------

public class Heap {
    private int size;
    private int[] data;
    private boolean mode_max; // true = max heap, false = min heap

/**
 *
 * @return ค่าที่มากหรือน้อยตามแต่จะกำหนดใน
 */
int dequeue(){
    if(size <= 0){
        throw new IndexOutOfBoundsException("out of value");
    }
    
    //TODO: หาข้อมูล

    //TODO: ย้ายข้อมูลไปตำแหน่งสุดท้าย


    int result =  data[size-1];
    // ลบข้อมูลตำแหน่งสุดท้าย
    decrease_array_data();

    // ทำการ sort ใหม่
    if(mode_max){
        sort_max_to_min();
    } else {
        sort_min_to_max();
    }

    return result;
}

/**
 *
 */
void sort_min_to_max(){
    // TODO: แก้ให้เรียงข้อมูลเวลาใช้ show_in_order ต้องเรียงจากน้อยไปมาก
   
}


/**
 *
 */
void sort_max_to_min(){
    // TODO: แก้ให้เรียงข้อมูลเวลาใช้ show_in_order ต้องเรียงจากมากไปน้อย
    
}

private void in_order_traversal(int index_start) {
    // TODO เขียน function นี้เพื่อให้เป็น in order
   
    System.out.print(data[index_start] + " ");

}


void enqueue(int value){
    // ทำ dynamic array ให้มีค่าและขนาดเพิ่มขึ้น 1
    increase_array_data();

    // เพิ่มข้อมูลไปตำแหน่งสุดท้าย
    data[size-1] = value;

    // ทำการ sort ใหม่
    if(mode_max){
        sort_max_to_min();
    } else {
        sort_min_to_max();
    }
}

void show_in_order() {
    System.out.print("[");
    in_order_traversal(0);
    System.out.println("]");
}


void show_array(){
    System.out.print("[");
    for(int i = 0; i < size; i ++){
        System.out.print(data[i]);
        if(i+1 < size){
            System.out.print(" ");
        }
    }
    System.out.println("]");
}

private int calculateHeapHeight(int n) {
    return  (int) Math.ceil(Math.log(n + 1) / Math.log(2));
}

void show_tree(){
    int i=0;
    int h = calculateHeapHeight(size);
    for(int lv = 1 ; lv <= h; lv++){
        for(int column = 0; column < Math.pow(2,lv-1) && i < size; column++){
            System.out.print(data[i]);
            i++;
            if(column < Math.pow(2,lv-1)){
                System.out.print(" ");
            }
        }
        System.out.println();
    }
}
Heap(){
    size = 0;
    data = null;
    setModeMax(false);
}

Heap(boolean mode){
    size = 0;
    data = null;
    setModeMax(mode);
}

/**
 * @function increase_array_data
 * เป็นฟังก์ชันในการเพิ่มขนาดของ Array ที่ชื่อ Data และค่า size
 */
private void increase_array_data(){
    int [] new_arr = new int[size+1];
    for(int i = 0 ; i < size; i++){
        new_arr[i] = data[i];
    }
    data = new_arr;
    // เพิ่มขนาดของ size
    size++;
}

/**
 * @function decrease_array_data
 * เป็นฟังก์ชันในการลดขนาดของ Array ที่ชื่อ Data และค่า size
 */
private void decrease_array_data(){
    int [] new_arr = new int[size-1];
    for(int i = 0; i < size-1; i++){
        new_arr[i] = data[i];
    }
    data=new_arr;
    // ลดขนาดของ size
    size--;
}

/**
 *
 * @param mode
 * ถ้า True คือกำหนดให้เรียงข้อมูลจากมากไปน้อย
 * ถ้าค่าเป็น False คือกำหนดให้เรียงข้อมูลจากน้อยไปมาก
 */
void setModeMax(boolean mode){
    mode_max = mode;
    if(size > 0) {
        if (mode_max) {
            sort_max_to_min();
        } else {
            sort_min_to_max();
        }
    }
}

void show_size(){
    System.out.println(size);
}

}




-------------

Main Class

-------------

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        String[] checker = new String[2];
        checker[0] = "1";
        Scanner input = new Scanner(System.in);
        Heap objbt = new Heap();
        do {
            checker = input.nextLine().split(" ");
            switch (Integer.parseInt(checker[0])) {
                case 0: // mode
                    objbt.setModeMax(Boolean.parseBoolean(checker[1]));
                    break;
                case 1: // insert
                    objbt.enqueue(Integer.parseInt(checker[1]));
                    break;
                case 2: // delete
                    try {
                        System.out.println(objbt.dequeue());
                    } catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 3: // print
                    objbt.show_size();
                    break;
                case 4: // print all
                    objbt.show_array();
                    break;
                case 5: // print tree
                    objbt.show_tree();
                    break;
                case 6: // print
                    objbt.show_in_order();
                    break;
            }
        } while (!checker[0].equals("-99"));
    }
}


โดยให้ input และ output ออกมาตามนี้
Example 1:
Input:
0 false
1 1
1 5
1 4
1 3
3
4
5
6
-99

Output:
4
[4 3 5 1]
4 
3 5 
1 
[1 3 4 5 ]

Example 2:
Input:
1 5
1 8
1 3
5
2
5
1 10
1 2
0 true
4
6
3
5
-99

Output:
5 
3 8 
3
8 
5 
[5 8 2 10]
[10 8 5 2 ]
4
5 
8 2 
10