Data Structure Quiz #9 Heap

คุณสมบัติที่เหมือนกันของ Binary Search Tree และ Heap ได้แก่อะไรบ้าง

• ใช้บันทึกข้อมูลที่เรียงลำดับได้

• เป็น Binary Tree

• ความสมดุลที่โหนดต่างๆในต้นไม้

• เลข index ของโหนดลูกเมื่อกำหนด index โหนดแม่เป็น i

คุณสมบัติสำคัญของ Heap คืออะไร

• Max Property

• Heap Property

• Shape Property

• Priority Property

• Tree Property

ข้อใดไม่จริงเกี่ยวกับ Min Heap อันเนื่องมาจาก Heap Property

• ค่าต่ำสุด จะอยู่ที่ Root Node

• ค่าในโหนดที่ i จะน้อยกว่าค่าในโหนดที่ 2i + 2

• ค่าในทุกโหนดในระดับที่ k น้อยกว่าค่าในทุกโหนดที่อยู่ระดับที่ k+1

• ค่าสูงสุดของข้อมูล จะอยู่ที่หนึ่งใน Leaf Node

ข้อใดจริงเกี่ยวกับ Heap ขนาด n ที่เป็นเหตุมาจาก Shape Property

• Worst Case ของการเข้าถึงข้อมูลเป็น O(n)

• ทุกๆโหนดมีค่าความสมดุล -1, 1, 0 เท่านั้น

• ถ้า n = 2^k จะมีความสูงเป็น k - 1

• ค่าสุดขีดจะอยู่ที่โหนด 0 และ โหนดที่ n - 1

ข้อใดเป็น Heap ที่ถูกต้อง

• 
• 
• 
• 

Time complexity ของการสร้าง Heap โดยที่มีข้อมูลนำเข้า n ตัวและ การทำ Heapify สูงสุดเมื่อเพิ่ม-ลดโหนด เป็นเท่าไหร่ ตามลำดับ

• สร้าง : O(n), Heapify : O(log n)

• สร้าง : O(log n), Heapify : O(log n)

• สร้าง : O(n log n), Heapify : O(log n)

• สร้าง : O(n log n), Heapify : O(n)

ข้อใด เป็นลักษณะของปัญหาที่ควรใช้ Priority Queue ที่สร้างจาก Heap ในการเก็บข้อมูล

• มีการเพิ่มลดข้อมูลได้ตลอดเวลา

• ต้องการค่าสูงสุด/ต่ำสุด 1 ตัวให้ออกจากข้อมูลได้ทันที

• มีค่า key เป็นตัวกำหนดลำดับการออก

• ต้องการเรียงข้อมูลจากค่า key มากไปน้อย

ข้อใดจริงเกี่ยวกับการใช้ Heap sort ในการเรียงลำดับข้อมูลจากน้อยไปมาก

• ในขั้นแรก จะสร้าง min heap โดยการใส่ข้อมูลทีละตัว

• ในขั้นที่ 2 จะนำข้อมูลที่ root node ออกจาก heap

• ในขั้นที่ 2 อาร์เรย์จะถูกแบ่งเป็น heap และ sorted array

• ในขั้นที่ 2 รอบที่ i จะได้ข้อมูลน้อยที่สุด i ลำดับเรียงแล้ว

ข้อใดจริงเกี่ยวกับ Heap sort

• เป็น in-place sort ที่ใช้ space เพิ่ม O(1)

• เป็น stable sort

• ใช้เวลาน้อยกว่าการทำ Quick sort เสมอ

• มีเวลใน average case เป็น O(n log n)

ข้อใดเป็นผลของขั้นต่อไป ของ ผลการทำ heap sort ในอาร์เรย์นี้

• 
• 
• 
•