การปรับใช้ลำดับความสำคัญโดยใช้ฮีปสูงสุดเทียบกับ BST ที่สมดุล
BST O(logn)สมดุลและกองสูงสุดทั้งดำเนินการแทรกและลบใน อย่างไรก็ตามการหาค่าสูงสุดในฮีปสูงสุดนั้นO(1)อยู่O(logn)ใน BST ที่สมดุล
หากเราลบค่าสูงสุดในฮีปสูงสุดจะใช้เวลาO(logn)เนื่องจากเป็นการดำเนินการลบ
ใน BST ที่สมดุลการลบองค์ประกอบสูงสุด = การค้นหาค่าสูงสุด + ลบ; มันเท่ากับ logn + logn O(logn)ลด ดังนั้นแม้การลบค่าสูงสุดใน BST O(logn)สมดุลเป็น
ฉันได้อ่านแอปพลิเคชั่นหนึ่งของฮีปสูงสุดดังกล่าวเป็นคิวลำดับความสำคัญและจุดประสงค์หลักคือการลบค่าสูงสุดสำหรับการดำเนินการ dequeue ทุกครั้ง หากการลบองค์ประกอบสูงสุดมีO(logn)ไว้สำหรับทั้งฮีปสูงสุดและ BST ที่สมดุลฉันมีคำถามต่อไปนี้
อะไรคือจุดประสงค์ของฮีปสูงสุดในคิวลำดับความสำคัญเพียงเพราะมันง่ายต่อการนำไปใช้แทนที่จะใช้ BST ที่สมดุลแบบค้นหาได้เต็มรูปแบบ?
เนื่องจากไม่มีการคำนวณปัจจัยสมดุลฮีปสูงสุดจึงเรียกได้ว่าเป็นต้นไม้ไบนารีที่ไม่สมดุล?
BST ที่สมดุลทุกรายการสามารถใช้เป็นคิวลำดับความสำคัญได้และสิ่งใดที่สามารถค้นหาได้ในการ
O(logn)ค้นหาฮีปสูงสุดที่O(n)ถูกต้อง
มีการคำนวณความซับซ้อนตลอดเวลาสำหรับกรณีที่เลวร้ายที่สุด ความช่วยเหลือใด ๆ ที่ได้รับการชื่นชมอย่างมาก
คำตอบ
อะไรคือจุดประสงค์ของฮีปสูงสุดในคิวลำดับความสำคัญเพียงเพราะมันง่ายต่อการนำไปใช้แทนที่จะใช้ BST ที่สมดุลแบบค้นหาได้เต็มรูปแบบ?
ข้อดีบางประการของฮีปคือ:
ได้รับการเข้าแถวเรียงลำดับเป็นกองยังคงสามารถสร้างขึ้นในO (n)เวลาขณะที่BST ต้องการO (nlogn)เวลา
หากอินพุตเริ่มต้นเป็นอาร์เรย์อาร์เรย์เดียวกันนั้นสามารถทำหน้าที่เป็นฮีปได้หมายความว่าไม่จำเป็นต้องใช้หน่วยความจำเพิ่มเติม แม้ว่าใครจะคิดวิธีสร้าง BST โดยใช้ข้อมูลในตำแหน่งในอาร์เรย์ได้ แต่ก็ค่อนข้างแปลก (สำหรับประเภทดั้งเดิม) และให้ค่าใช้จ่ายในการประมวลผลมากขึ้น โดยปกติแล้ว BST จะถูกสร้างขึ้นตั้งแต่ต้นโดยคัดลอกข้อมูลลงในโหนดเมื่อสร้างขึ้น
ข้อเท็จจริงที่น่าสนใจ: อาร์เรย์ที่เรียงลำดับก็เป็นฮีปเช่นกันดังนั้นหากทราบว่ามีการจัดเรียงข้อมูลเข้าก็ไม่จำเป็นต้องทำอะไรเพื่อสร้างฮีป
ฮีปสามารถจัดเก็บเป็นอาร์เรย์ได้โดยไม่จำเป็นต้องจัดเก็บการอ้างอิงข้ามในขณะที่ BST มักประกอบด้วยโหนดที่มีการอ้างอิงซ้ายและขวา สิ่งนี้มีผลอย่างน้อยสองประการ:
- หน่วยความจำที่ใช้สำหรับ BST นั้นมากกว่าฮีปประมาณ 3 เท่า
- แม้ว่าการดำเนินการหลายอย่างจะมีความซับซ้อนในเวลาเดียวกันสำหรับทั้งฮีปและ BST แต่ค่าโสหุ้ยสำหรับการปรับ BST จะมากกว่ามากดังนั้นเวลาจริงที่ใช้ในการดำเนินการเหล่านี้จึงเป็นปัจจัย (ค่าคงที่) มากกว่าในกรณี BST
เนื่องจากไม่มีการคำนวณปัจจัยสมดุลฮีปสูงสุดจึงเรียกได้ว่าเป็นต้นไม้ไบนารีที่ไม่สมดุล?
ในความเป็นจริงฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์ดังนั้นจึงมีความสมดุลเสมอเท่าที่จะเป็นไปได้: ใบไม้จะอยู่ในตำแหน่งสุดท้ายหรือระดับหนึ่ง แต่สุดท้ายเสมอ BST ที่ปรับสมดุลในตัวเอง (เช่น AVL, แดง - ดำ, ... ) ไม่สามารถเอาชนะความสมดุลในระดับสูงได้ซึ่งคุณมักจะมีใบไม้เกิดขึ้นที่สามระดับหรือมากกว่านั้น
BST ที่สมดุลทุกตัวสามารถใช้เป็นคิวลำดับความสำคัญและสิ่งใดที่ค้นหาได้ใน O (logn) อย่างไรก็ตามการค้นหาฮีปสูงสุด O (n) ถูกต้องหรือไม่
ใช่นี่เป็นเรื่องจริง ดังนั้นหากแอปพลิเคชันต้องการคุณสมบัติการค้นหา BST จะดีกว่า
อะไรคือจุดประสงค์ของฮีปสูงสุดในคิวลำดับความสำคัญเพียงเพราะมันง่ายต่อการนำไปใช้แทนที่จะใช้ BST ที่สมดุลแบบค้นหาได้เต็มรูปแบบ?
ไม่ ฮีปสูงสุดเหมาะสมกว่าเนื่องจากมีการใช้อย่างระมัดระวังเพื่อส่งคืนองค์ประกอบถัดไป (ตามลำดับความสำคัญ) โดยเร็วในเวลา O (1) นั่นคือสิ่งที่คุณต้องการจากคิวลำดับความสำคัญที่ง่ายที่สุด
เนื่องจากไม่มีการคำนวณปัจจัยสมดุลฮีปสูงสุดจึงเรียกได้ว่าเป็นต้นไม้ไบนารีที่ไม่สมดุล?
ไม่ มีความสมดุลเช่นกัน เรื่องสั้นขนาดยาวการปรับสมดุลฮีปทำได้โดยการเลื่อนขึ้นหรือเลื่อนลง (การสลับองค์ประกอบที่ไม่เป็นระเบียบ)
BST ที่สมดุลทุกตัวสามารถใช้เป็นคิวลำดับความสำคัญและสิ่งใดที่ค้นหาได้ใน O (logn) อย่างไรก็ตามการค้นหาฮีปสูงสุด O (n) ถูกต้องหรือไม่
ใช่ เช่นเดียวกับรายการที่เชื่อมโยงสามารถใช้หรืออาร์เรย์ มันจะแพงกว่าในแง่ของ O-notation และช้ากว่ามากในการฝึกฝน