Queap
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಕ್ಯೂಪ್ ಆದ್ಯತೆಯ ಕ್ಯೂ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದೆ. ದತ್ತಾಂಶ ರಚನೆಯು ಅನಿಯಂತ್ರಿತ ಅಂಶಗಳನ್ನು ಸೇರಿಸಲು ಮತ್ತು ಅಳಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಜೊತೆಗೆ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯ ಅಂಶವನ್ನು ಮರುಪಡೆಯಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಪ್ರತಿಯೊಂದು ಅಳಿಸುವಿಕೆಯು ತೆಗೆದುಹಾಕಲಾದ ವಸ್ತುವಿಗಿಂತ ದೀರ್ಘಕಾಲದವರೆಗೆ ರಚನೆಯಲ್ಲಿರುವ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಅಮೋರ್ಟೈಸ್ಡ್ ಟೈಮ್ ಲಾಗರಿಥಮಿಕ್ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಒಳಸೇರಿಸುವಿಕೆಯು ಸ್ಥಿರವಾದ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ದತ್ತಾಂಶ ರಚನೆಯು ದ್ವಿಗುಣವಾಗಿ ಜೋಡಿಸಲಾದ ಪಟ್ಟಿ ಮತ್ತು 2 ರಿಂದ 4 ಮರಗಳ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಪ್ರತಿಯೊಂದೂ ಅದರ ಕನಿಷ್ಠ-ಆದ್ಯತೆಯ ಅಂಶವನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡಲು ಮಾರ್ಪಡಿಸಲಾಗಿದೆ. ಈ ರಚನೆಯ ಮೂಲ ಕಾರ್ಯವೆಂದರೆ ಹೊಸದಾಗಿ ಸೇರಿಸಲಾದ ಅಂಶಗಳನ್ನು ದ್ವಿಗುಣವಾಗಿ ಜೋಡಿಸಲಾದ ಪಟ್ಟಿಯಲ್ಲಿ ಇಡುವುದು, ಒಂದು ಅಳಿಸುವಿಕೆಯು ಪಟ್ಟಿಯ ಪದಾರ್ಥಗಳಲ್ಲಿ ಒಂದನ್ನು ತೆಗೆದುಹಾಕುವವರೆಗೆ, ಆ ಸಮಯದಲ್ಲಿ ಅವೆಲ್ಲವನ್ನೂ 2 ರಿಂದ 4 ಮರಕ್ಕೆ ಸ್ಥಳಾಂತರಿಸಲಾಗುತ್ತದೆ. 2-4 ಮರವು ಅದರ ಅಂಶಗಳನ್ನು ಹೆಚ್ಚು ಸಾಂಪ್ರದಾಯಿಕ ಆದ್ಯತೆಯ ಕ್ರಮಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿ ಅಳವಡಿಸುವ ಕ್ರಮದಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತದೆ. ದತ್ತಾಂಶ ರಚನೆ ಮತ್ತು ಅದರ ಹೆಸರು ಎರಡನ್ನೂ ಜಾನ್ ಇಕಾನೊ ಮತ್ತು ಸ್ಟೀಫನ್ ಲ್ಯಾಂಗರ್ಮನ್ ರೂಪಿಸಿದರು. ವಿವರಣೆ ಕ್ಯೂಪ್ ಎನ್ನುವುದು ಒ (1) ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯದಲ್ಲಿ ಅಂಶಗಳನ್ನು ಸೇರಿಸುವ ಆದ್ಯತೆಯ ಸರತಿಯಾಗಿದೆ ಮತ್ತು ಹೊರತೆಗೆಯಬೇಕಾದ ಅಂಶಕ್ಕಿಂತ ಹೆಚ್ಚು ಸಮಯದವರೆಗೆ ರಾಶಿಯಲ್ಲಿದ್ದ ಕೆ ಐಟಂಗಳು ಇದ್ದರೆ ಒ (ಲಾಗ್ (ಕೆ + 2)) ನಲ್ಲಿನ ಕನಿಷ್ಠ ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ. ಕ್ಯೂಯಾಪ್ ಕ್ಯೂಯಿಶ್ ಪ್ರಾಪರ್ಟಿ ಎಂಬ ಗುಣವನ್ನು ಹೊಂದಿದೆಃ x ಅಂಶವನ್ನು ಹುಡುಕುವ ಸಮಯವು O (lg q (x)) ಆಗಿದೆ, ಅಲ್ಲಿ q (x) ಎಂಬುದು n − 1 − w (x) ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ ಮತ್ತು w (x) ಎಂಬುದು ಹುಡುಕಾಟ, ಸೇರಿಸುವಿಕೆ ಅಥವಾ ಅಳಿಸುವಿಕೆಯಂತಹ ಕಾರ್ಯಾಚರಣೆಗಳ ಮೂಲಕ ಪ್ರವೇಶಿಸಲಾದ ವಿಭಿನ್ನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. q (x) ಅನ್ನು x ನ ಕೊನೆಯ ಪ್ರವೇಶದ ನಂತರ ಎಷ್ಟು ಅಂಶಗಳನ್ನು ಪ್ರವೇಶಿಸಲಾಗಿಲ್ಲ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ವಾಸ್ತವವಾಗಿ, ಕ್ಯೂಯಿಶ್ ಗುಣಲಕ್ಷಣವು ಸ್ಪ್ಲೇ ಟ್ರೀ ವರ್ಕಿಂಗ್ ಸೆಟ್ ಗುಣಲಕ್ಷಣದ ಪೂರಕವಾಗಿದೆಃ x ಅಂಶವನ್ನು ಹುಡುಕುವ ಸಮಯವು O (lg w (x)) ಆಗಿದೆ. ಕ್ಯೂಪ್ಅನ್ನು ಎರಡು ದತ್ತಾಂಶ ರಚನೆಗಳ ಮೂಲಕ ಪ್ರತಿನಿಧಿಸಬಹುದುಃ ಡಬಲ್ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಮತ್ತು 2-4 ಟ್ರೀನ ಮಾರ್ಪಡಿಸಿದ ಆವೃತ್ತಿ. ಡಬಲ್ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್, ಎಲ್, ಅನ್ನು ಇನ್ಸರ್ಟ್ ಮತ್ತು ಲೊಕೇಟ್-ಮಿನ್ ಕಾರ್ಯಾಚರಣೆಗಳ ಸರಣಿಗಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಕ್ಯೂಪ್ ಪಟ್ಟಿಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಕನಿಷ್ಠ ಅಂಶಕ್ಕೆ ಪಾಯಿಂಟರ್ ಅನ್ನು ಇರಿಸುತ್ತದೆ. l ಅನ್ನು ಪಟ್ಟಿ ಮಾಡಲು x ಅಂಶವನ್ನು ಸೇರಿಸಲು, x ಅಂಶವನ್ನು ಪಟ್ಟಿಯ ಕೊನೆಯಲ್ಲಿ ಸೇರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು x ಅಂಶದಲ್ಲಿ ಸ್ವಲ್ಪ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಒಂದಕ್ಕೆ ಹೊಂದಿಸಲಾಗುತ್ತದೆ. ಅಂಶವು ಪಟ್ಟಿಯಲ್ಲಿದೆಯೇ ಅಥವಾ 2-4 ಮರದಲ್ಲಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸಲು ಈ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಮಾಡಲಾಗುತ್ತದೆ. ಅಳಿಸುವ ಕಾರ್ಯಾಚರಣೆಯು ಸಂಭವಿಸಿದಾಗ 2-4 ಮರವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಐಟಂ x ಈಗಾಗಲೇ ಟ್ರೀ ಟಿ ಯಲ್ಲಿದ್ದರೆ, 2-4 ಟ್ರೀ ಡಿಲೀಟ್ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಐಟಂ ಅನ್ನು ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಐಟಂ x ಪಟ್ಟಿ L ನಲ್ಲಿದೆ (ಬಿಟ್ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಹೊಂದಿಸಲಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಮಾಡಲಾಗುತ್ತದೆ). ಎಲ್ ಪಟ್ಟಿಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ನಂತರ 2-4 ಮರಕ್ಕೆ ಸೇರಿಸಲಾಗುತ್ತದೆ, ಪ್ರತಿ ಅಂಶದ ಬಿಟ್ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಲಾಗುತ್ತದೆ. ನಂತರ ಟಿ ಯಿಂದ ಎಕ್ಸ್ ಅನ್ನು ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ. ಕ್ಯೂಪ್ 2-4 ಮರದ ರಚನೆಯ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತದೆ, ಸರ್ಚ್ ಟ್ರೀ ಅಲ್ಲ. ಮಾರ್ಪಡಿಸಿದ 2-4 ಮರದ ರಚನೆಯು ಈ ಕೆಳಗಿನಂತಿದೆ. ಪಟ್ಟಿ ಎಲ್ ಈ ಕೆಳಗಿನ ಅಂಶಗಳ ಗುಂಪನ್ನು ಹೊಂದಿದೆ ಎಂದು ಭಾವಿಸೋಣಃ ಅಳಿಸುವ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಪ್ರಾರಂಭಿಸಿದಾಗ, ಎಲ್ನಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಅಂಶಗಳ ಗುಂಪನ್ನು ಆ ಕ್ರಮದಲ್ಲಿ 2-4 ಮರದ ಎಲೆಗಳಿಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ, ಅನಂತ ಕೀಲಿಯನ್ನು ಹೊಂದಿರುವ ನಕಲಿ ಎಲೆಯಿಂದ ಮುಂದುವರಿಯುತ್ತದೆ. ಟಿ ಯ ಪ್ರತಿಯೊಂದು ಆಂತರಿಕ ನೋಡ್ ಒಂದು ಪಾಯಿಂಟರ್ ಅನ್ನು ಹೊಂದಿದೆ, ಇದು ಸಬ್ಟ್ರೀ ವಿ ನಲ್ಲಿನ ಚಿಕ್ಕ ವಸ್ತುವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಪಿ ಮಾರ್ಗದಲ್ಲಿರುವ ಪ್ರತಿ ಆಂತರಿಕ ನೋಡ್ ಮೂಲದಿಂದ ಪಾಯಿಂಟರ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಇದು ಚಿಕ್ಕ ಕೀಲಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಪಿ ಮಾರ್ಗದಲ್ಲಿರುವ ಪ್ರತಿ ಆಂತರಿಕ ನೋಡ್ನ ಪಾಯಿಂಟರ್ಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸಲಾಗುತ್ತದೆ. ಕ್ಯೂಪ್ ಒಂದು ಪಾಯಿಂಟರ್ ಅನ್ನು ಹೊಂದಿದೆ, ಇದು ಟಿ ಯಲ್ಲಿನ ಚಿಕ್ಕ ಅಂಶವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಕ್ಯೂಪ್ಗಳ ಅನ್ವಯವು ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯ ಘಟನೆಗಳ ವಿಶಿಷ್ಟ ಗುಂಪನ್ನು ಮತ್ತು ಸಂಸ್ಕರಣೆಗಾಗಿ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯ ಘಟನೆಯ ಹೊರತೆಗೆಯುವಿಕೆಯನ್ನು ಒಳಗೊಂಡಿದೆ. ಕಾರ್ಯಾಚರಣೆಗಳು ಮಿನಿಎಲ್ ಡಬಲ್ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಎಲ್ನಲ್ಲಿನ ಕನಿಷ್ಠ ಅಂಶವನ್ನು ಸೂಚಿಸುವ ಪಾಯಿಂಟರ್ ಆಗಿರಲಿ, 2-4 ಟ್ರೀಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಕನಿಷ್ಠ ಅಂಶವಾಗಿರಲಿ, ಟಿ, ಕೆ ಟಿ ಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಅಂಶಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ, ಮತ್ತು ಎನ್ ಕ್ಯೂಪ್ ಕ್ಯೂ ನಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಅಂಶಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯಾಗಿರಲಿ. ಕಾರ್ಯಾಚರಣೆಗಳು ಈ ಕೆಳಗಿನಂತಿವೆಃ ಹೊಸ (ಕ್ಯೂ): ಹೊಸ ಖಾಲಿ ಕ್ಯೂಪ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸುತ್ತದೆ. ಖಾಲಿ ಡಬಲ್ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಎಲ್ ಮತ್ತು 2-4 ಟ್ರೀ ಟಿ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ. ಕೆ ಮತ್ತು ಎನ್ ಅನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಿ. ಸೇರಿಸು (ಕ್ಯೂ, ಎಕ್ಸ್): ಕ್ಯೂಪ್ ಕ್ಯೂಗೆ x ಅಂಶವನ್ನು ಸೇರಿಸಿ. ಎಲ್ ಪಟ್ಟಿಯಲ್ಲಿ x ಅಂಶವನ್ನು ಸೇರಿಸಿ. ಎಲ್ ಪಟ್ಟಿಯಲ್ಲಿ ಅಂಶವು ಇದೆ ಎಂದು ತೋರಿಸಲು x ಅಂಶದಲ್ಲಿ ಬಿಟ್ ಅನ್ನು ಒಂದಕ್ಕೆ ಹೊಂದಿಸಿ. ಪಟ್ಟಿಯಲ್ಲಿ x ಚಿಕ್ಕ ಅಂಶವಾಗಿದ್ದರೆ ಮಿನ್ಎಲ್ ಪಾಯಿಂಟರ್ ಅನ್ನು ನವೀಕರಿಸಿ. n ಅನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ. ಕನಿಷ್ಠ (ಕ್ಯೂ): ಕ್ಯೂಪ್ ಕ್ಯೂ ನಿಂದ ಚಿಕ್ಕ ಅಂಶಕ್ಕೆ ಪಾಯಿಂಟರ್ ಅನ್ನು ಹಿಂಪಡೆಯಿರಿ. ಕೀಲಿಯು (ಮಿನ್ಎಲ್) <ಕೀ () ಆಗಿದ್ದರೆ, ಮಿನ್ಎಲ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸಿ. ಇಲ್ಲದಿದ್ದರೆ ಹಿಂತಿರುಗಿ. ಅಳಿಸಿ (ಕ್ಯೂ, ಎಕ್ಸ್): ಕ್ಯೂಪ್ ಕ್ಯೂ ನಿಂದ x ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕಿ. x ಅಂಶದ ಬಿಟ್ ಅನ್ನು ಒಂದಕ್ಕೆ ಹೊಂದಿಸಿದರೆ, ಅಂಶವನ್ನು ಎಲ್ ಪಟ್ಟಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. ಎಲ್ ನಿಂದ ಟಿ ವರೆಗಿನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸೇರಿಸಿ, ಪ್ರತಿ ಅಂಶದ ಬಿಟ್ ಅನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಿ. 2-4 ಮರದ ಇನ್ಸರ್ಟ್ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಟಿ ಯ ಬಲಭಾಗದ ಮಗುವಿನ ಪೋಷಕರಿಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಎಲ್ ಖಾಲಿಯಾಗುತ್ತದೆ. ಮಕ್ಕಳು ಹೊಸ/ಮಾರ್ಪಡಿಸಿದ ಎಲ್ಲಾ ನೋಡ್ಗಳಿಗೆ ಪಾಯಿಂಟರ್ಗಳನ್ನು ನವೀಕರಿಸಿ, ಮತ್ತು ಪೋಷಕರು ಮೂಲಕ್ಕೆ ಸಮಾನವಾಗುವವರೆಗೆ ಮುಂದಿನ ಪೋಷಕರೊಂದಿಗೆ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಿ. ಮೂಲದಿಂದ ನೋಡ್ಗೆ ಹೋಗಿ, ಮೌಲ್ಯಗಳನ್ನು ನವೀಕರಿಸಿ. k ಅನ್ನು n ಗೆ ಸಮನಾಗಿ ಹೊಂದಿಸಿ. x ಅಂಶದ ಬಿಟ್ ಅನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಿದರೆ, x ಎಂಬುದು T ಯ ಎಲೆಯಾಗಿದೆ. 2-4 ಟ್ರೀ ಡಿಲೀಟ್ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು x ಅನ್ನು ಅಳಿಸಿ. ನೋಡ್ x ನಿಂದ ಪ್ರಾರಂಭಿಸಿ, T ಯಿಂದ ನೋಡ್ಗೆ ಹೋಗಿ, ನವೀಕರಿಸಿ ಮತ್ತು ಪಾಯಿಂಟರ್ಗಳನ್ನು ಮಾಡಿ. n ಮತ್ತು k ಅನ್ನು 1 ರಿಂದ ಕಡಿಮೆ ಮಾಡಿ. ಡಿಲೀಟ್ಮಿನ್ (ಕ್ಯೂ): ಕ್ಯೂಪ್ ಕ್ಯೂ ನಿಂದ ಚಿಕ್ಕ ಅಂಶವನ್ನು ಅಳಿಸಿ ಹಿಂತಿರುಗಿಸಿ. ಕನಿಷ್ಠ (ಕ್ಯೂ) ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಆಹ್ವಾನಿಸಿ. ಕಾರ್ಯಾಚರಣೆಯು ನಿಮಿಷವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಅಳಿಸಿ (ಕ್ಯೂ, ನಿಮಿಷ) ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಆಹ್ವಾನಿಸಿ. ಮಿನಿ ಹಿಂತಿರುಗಿ. ಕ್ಲೀನ್ಅಪ್ (ಕ್ಯೂ): ಎಲ್ ಮತ್ತು ಟ್ರೀ ಟಿ ಪಟ್ಟಿಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಅಳಿಸಿ. ಎಲ್ ಪಟ್ಟಿಯಲ್ಲಿರುವ ಮೊದಲ ಅಂಶದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಪ್ರತಿ ನೋಡ್ ಅನ್ನು ಅಳಿಸಿ, ಪಟ್ಟಿಯನ್ನು ಹಾದುಹೋಗಿ. ಟಿ ಮರದ ಮೂಲದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಮರದ ಪ್ರತಿ ನೋಡ್ ಅನ್ನು ಅಳಿಸಿ, ಪೋಸ್ಟ್-ಆರ್ಡರ್ ಟ್ರಾವರ್ಸಲ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಮರವನ್ನು ಹಾದುಹೋಗಿ. ವಿಶ್ಲೇಷಣೆ ಸಾಲ ಮರುಪಾವತಿ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ವಿಶ್ಲೇಷಿಸಲಾಗುತ್ತದೆ. ಕ್ಯೂಪ್ ಕ್ಯೂಗೆ ಸಂಭಾವ್ಯ ಕಾರ್ಯವು ಎಲ್ಲಿರುತ್ತದೆ. ಇನ್ಸರ್ಟ್ (ಕ್ಯೂ, ಎಕ್ಸ್): ಕಾರ್ಯಾಚರಣೆಯ ವೆಚ್ಚವು ಒ (1) ಆಗಿದೆ. ಪಟ್ಟಿ ಎಲ್ ನ ಗಾತ್ರವು ಒಂದೊಂದಾಗಿ ಬೆಳೆಯುತ್ತದೆ, ಸಂಭಾವ್ಯತೆಯು ಕೆಲವು ಸ್ಥಿರತೆಯಿಂದ ಹೆಚ್ಚಾಗುತ್ತದೆ ಸಿ. ಕನಿಷ್ಠ (ಕ್ಯೂ): ಕಾರ್ಯಾಚರಣೆಯು ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಬದಲಾಯಿಸುವುದಿಲ್ಲ ಆದ್ದರಿಂದ ಸಾಲ ಮರುಪಾವತಿ ವೆಚ್ಚವು ಅದರ ನಿಜವಾದ ವೆಚ್ಚವಾದ ಒ (1) ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಅಳಿಸಿ (ಕ್ಯೂ, ಎಕ್ಸ್): ಎರಡು ಪ್ರಕರಣಗಳಿವೆ. ಪ್ರಕರಣ 1 x ಟ್ರೀ Tಯಲ್ಲಿದ್ದರೆ, ಆಮೋರ್ಟೈಸ್ಡ್ ವೆಚ್ಚವನ್ನು ಮಾರ್ಪಡಿಸಲಾಗುವುದಿಲ್ಲ. ಅಳಿಸುವ ಕಾರ್ಯಾಚರಣೆಯು ಓ (1) ಅಮೋರ್ಟೈಸ್ಡ್ 2-4 ಟ್ರೀ ಆಗಿದೆ. ಮರದಿಂದ x ಅನ್ನು ತೆಗೆದುಹಾಕಲಾಗಿರುವುದರಿಂದ, ಪಾಯಿಂಟರ್ಗಳನ್ನು ನವೀಕರಿಸುವ ಅಗತ್ಯವಿರಬಹುದು. ಹೆಚ್ಚುಕಡಿಮೆ, ನವೀಕರಣಗಳು ಇರುತ್ತವೆ. ಪ್ರಕರಣ 2 x L ಪಟ್ಟಿಯಲ್ಲಿದ್ದರೆ, L ನಿಂದ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು T ಯಲ್ಲಿ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಇದು 2 ರಿಂದ 4 ಮರಗಳ ಮೇಲೆ ಸಾಲ ಮರುಪಾವತಿ ಮಾಡುವ ಕೆಲವು ಸ್ಥಿರಾಂಕದ ವೆಚ್ಚವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಮತ್ತು ಪಾಯಿಂಟರ್ಗಳನ್ನು ಸೇರಿಸಿದ ಮತ್ತು ನವೀಕರಿಸಿದ ನಂತರ, ಕಳೆದ ಒಟ್ಟು ಸಮಯವನ್ನು ಈ ಕೆಳಗಿನವುಗಳಿಂದ ಸೀಮಿತಗೊಳಿಸಲಾಗಿದೆ. ಎರಡನೇ ಕಾರ್ಯಾಚರಣೆಯು ಟಿ ಯಿಂದ x ಅನ್ನು ಅಳಿಸುವುದು, ಮತ್ತು x ನಿಂದ x ಗೆ ಹೋಗುವ ಹಾದಿಯಲ್ಲಿ ನಡೆಯುವುದು, ಮತ್ತು ಮೌಲ್ಯಗಳನ್ನು ಸರಿಪಡಿಸುವುದು. ಹೆಚ್ಚಿನ ಸಮಯವನ್ನು ವ್ಯಯಿಸಲಾಗುತ್ತದೆ. ಇದ್ದರೆ, ಆಮೋರ್ಟೈಸ್ಡ್ ವೆಚ್ಚವು ಆಗಿರುತ್ತದೆ. ಅಳಿಸಿ (ಕ್ಯೂ, ಎಕ್ಸ್): ಇದು ಕನಿಷ್ಠ (ಕ್ಯೂ) ಮತ್ತು ಅಳಿಸಿ (ಕ್ಯೂ, ಎಕ್ಸ್) ನ ಮರುಪಾವತಿ ವೆಚ್ಚದ ಸೇರ್ಪಡೆಯಾಗಿದೆ. ಕೋಡ್ ಉದಾಹರಣೆ ಕ್ಯೂಪ್ನ ಒಂದು ಸಣ್ಣ ಜಾವಾ ಅನುಷ್ಠಾನಃ ಸಾರ್ವಜನಿಕ ವರ್ಗದ ಕ್ಯೂಪ್ {ಸಾರ್ವಜನಿಕ ಇಂಟ್ ಎನ್, ಕೆ; ಸಾರ್ವಜನಿಕ ಪಟ್ಟಿ <ಎಲಿಮೆಂಟ್> ಎಲ್;// ಎಲಿಮೆಂಟ್ ಒಂದು ಸಾಮಾನ್ಯ ದತ್ತಾಂಶ ಪ್ರಕಾರವಾಗಿದೆ. ಸಾರ್ವಜನಿಕ ಕ್ಯೂಯಾಪ್ಟ್ರೀ ಟಿ;// 2-4 ಮರ, ಕ್ಯೂಯಾಪ್ ಉದ್ದೇಶಕ್ಕಾಗಿ ಮಾರ್ಪಡಿಸಲಾದ ಸಾರ್ವಜನಿಕ ಅಂಶ ಮಿನಿಎಲ್; ಖಾಸಗಿ ಕ್ಯೂಯಾಪ್ () {n = 0; k = 0; l = ಹೊಸ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ <ಎಲಿಮೆಂಟ್> (); t = ಹೊಸ ಕ್ಯೂಯಾಪ್ಟ್ರೀ ();} ಸಾರ್ವಜನಿಕ ಸ್ಥಿರ ಕ್ಯೂಯಾಪ್ ಹೊಸ () {ರಿಟರ್ನ್ ನ್ಯೂ ಕ್ಯೂಯಾಪ್ ();} ಸಾರ್ವಜನಿಕ ಸ್ಥಿರ ಶೂನ್ಯ ಇನ್ಸರ್ಟ್ (ಕ್ಯೂಯಾಪ್ ಕ್ಯೂ, ಎಲಿಮೆಂಟ್ x) {(ಕ್ಯೂ. ಎನ್ = = = 0) Q.minL = x; Q.l.add (x); x.inList = ನಿಜ; (x.compareTo (Q.minL) <0) Q.minL = x;} ಸಾರ್ವಜನಿಕ ಸ್ಥಿರ ಅಂಶ ಕನಿಷ್ಠ (ಕ್ಯೂಯಾಪ್ ಕ್ಯೂ) (Q.minL.compareTo (Q.t.x0.cv. ಕೀ) <0) ಹಿಂದಿರುಗಿಸಿದರೆ Q.minL; ಹಿಂದಿರುಗಿಸಿದರೆ Q.t.x0.cv. ಕೀ;} ಸಾರ್ವಜನಿಕ ಸ್ಥಿರ ಶೂನ್ಯ ಅಳಿಸಿ (ಕ್ಯೂಯಾಪ್ ಕ್ಯೂ, ಕ್ಯೂಯಾಪ್ನೋಡ್ x) {Q.t.deleteLeaf (x);-- ಕ್ಯೂ. ಎನ್.;-- ಕ್ಯೂ. ಕೆ.;} ಸಾರ್ವಜನಿಕ ಸ್ಥಿರ ಶೂನ್ಯ ಅಳಿಸಿ (ಕ್ಯೂಯಾಪ್ ಕ್ಯೂ, ಎಲಿಮೆಂಟ್ x) {ಕ್ಯೂಯಾಪ್ನೋಡ್ ಎನ್; (x.inList) {// ಪಟ್ಟಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡಿ ತಪ್ಪು n = Q.t.insertList (ಕ್ಯೂ. ಎಲ್, ಎಕ್ಸ್); ಕ್ಯೂ. ಕೆ. = ಕ್ಯೂ. ಎನ್.; ಅಳಿಸಿ (ಕ್ಯೂ, ಎನ್); ಇಲ್ಲದಿದ್ದರೆ ((ಎನ್ = Q.t.x0.cv).