\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u043e\u0442\u0447\u0451\u0442\u0435 \u044f \u043d\u0430\u043f\u0438\u0448\u0443 \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u0443\u0447\u0430 (Heap), \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 — \u043e \u0435\u0451 \u0440\u0430\u0437\u043d\u043e\u0432\u0438\u0434\u043d\u043e\u0441\u0442\u0438.<\/p>\n
\u0414\u0432\u043e\u0438\u0447\u043d\u0430\u044f \u043a\u0443\u0447\u0430<\/em> — \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u0442\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f:<\/p>\n \u0417\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u0442\u044c \u043d\u0430\u0434 \u043a\u0443\u0447\u0435\u0439:<\/p>\n 1. \u0412\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u043a\u0443\u0447\u0438<\/strong><\/em><\/p>\n \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0435\u0446 \u043a\u0443\u0447\u0438, \u043f\u043e\u0442\u043e\u043c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u0430 \u0441\u0432\u043e\u0451 \u043c\u0435\u0441\u0442\u043e, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432 \u043a\u0443\u0447\u0438.<\/p>\n \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c:<\/em> [latex]O(\\log(n))[\/latex]\n 2. \u0412\u043e\u0437\u0432\u0440\u0430\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430<\/strong><\/em><\/p>\n \u0412\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442\u044c \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u0435 \u0441\u0430\u043c\u043e\u0439 \u0432\u0435\u0440\u0445\u043d\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c:<\/em> [latex]O(1)[\/latex]\n 3. \u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430<\/strong><\/em><\/p>\n \u041c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u043f\u0435\u0440\u0432\u0430\u044f \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044f\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044f\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f, \u0430 \u043d\u043e\u0432\u0430\u044f \u043f\u0435\u0440\u0432\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043f\u0440\u043e\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u0443\u0447\u0443, \u0441\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u0435\u0451 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c.<\/p>\n \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c:<\/em> [latex]O(\\log(n))[\/latex]\n 4. \u041f\u0438\u0440\u0430\u043c\u0438\u0434\u0430\u043b\u044c\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/strong><\/em><\/p>\n \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0432 \u0441\u0430\u043c\u0443\u044e \u043f\u0435\u0440\u0432\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u043a\u0443\u0447\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 (\u043f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435, \u043f\u043e \u0432\u0432\u0435\u0434\u0451\u043d\u043d\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c) \u0432\u0441\u0442\u0430\u0451\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. \u0415\u0441\u043b\u0438 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 — \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432.<\/p>\n \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c:<\/em> [latex]O(n\\log(n))[\/latex]\n \u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0441 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u043c \u0442\u0438\u043f\u043e\u043c \u0434\u0430\u043d\u043d\u044b\u0445. \u00a0\u0414\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u0448\u0438\u043d \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c ArrayList. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043f\u043e\u0434 \u043d\u043e\u043c\u0435\u0440\u043e\u043c [latex]i[\/latex] \u0435\u0451 \u043b\u0435\u0432\u044b\u0439 \u0441\u044b\u043d \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432\u00a0[latex]2*i+1[\/latex] \u0432\u0435\u0440\u0448\u0438\u043d\u0435, \u0430 \u043f\u0440\u0430\u0432\u044b\u0439 — \u0432\u00a0[latex]2*i+2[\/latex] \u0432\u0435\u0440\u0448\u0438\u043d\u0435.<\/p>\n \u041a\u043b\u0430\u0441\u0441 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u044b:<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" \u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u043e\u0442\u0447\u0451\u0442\u0435 \u044f \u043d\u0430\u043f\u0438\u0448\u0443 \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u0443\u0447\u0430 (Heap), \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 — \u043e \u0435\u0451 \u0440\u0430\u0437\u043d\u043e\u0432\u0438\u0434\u043d\u043e\u0441\u0442\u0438. \u0414\u0432\u043e\u0438\u0447\u043d\u0430\u044f \u043a\u0443\u0447\u0430 \u0414\u0432\u043e\u0438\u0447\u043d\u0430\u044f \u043a\u0443\u0447\u0430 — \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u0442\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f: \u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043b\u044e\u0431\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u0445 \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u043e \u043a\u043e\u0440\u043d\u044f \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u043d\u0430 \u043e\u0434\u0438\u043d \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0432\u0430 \u043d\u0430 … Continue reading \n
\n
\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432<\/h2>\n
\u041e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438<\/h2>\n
\n
\u041a\u043e\u0434<\/h3>\n
import java.util.*;\r\nimport java.lang.*;\r\nimport java.io.*;\r\n \r\nclass Heap <T extends Comparable<T> > {\r\n \/\/arraylist is much better than an array. There is no need to carry about a capacity.\r\n private ArrayList<T> items;\r\n \r\n \/\/construct\r\n public Heap() {\r\n items = new ArrayList<T> (); \r\n }\r\n \r\n \/\/using shiftUp for insert. \r\n private void shiftUp () {\r\n int k = items.size() - 1;\r\n while (k > 0){\r\n int curr = (k-1)\/2;\r\n T Item = items.get(k);\r\n T Parent = items.get(curr);\r\n if (Item.compareTo(Parent) > 0){\r\n items.set(k, Parent);\r\n items.set(curr, Item);\r\n k = curr;\r\n }\r\n else break;\r\n }\r\n }\r\n \r\n \/\/using shiftDown fo delete\r\n private void shiftDown() {\r\n int curr = 0; \r\n int leftChild = 2*curr+1;\r\n while (leftChild < items.size()) {\r\n int max = leftChild;\r\n int rightChild = leftChild + 1;\r\n if (rightChild < items.size()) {\r\n if (items.get(rightChild).compareTo(items.get(1)) > 0) {\r\n ++max;\r\n }\r\n }\r\n if (items.get(curr).compareTo(items.get(max)) < 0) {\r\n T tmp = items.get(curr);\r\n items.set(curr, items.get(max));\r\n items.set(max, tmp);\r\n curr = max;\r\n leftChild = 2*curr+1;\r\n }\r\n else break;\r\n }\r\n }\r\n \r\n public void insert(T item) {\r\n items.add(item);\r\n shiftUp();\r\n }\r\n \r\n public T delete() throws NoSuchElementException {\r\n if (items.size() == 0) {\r\n throw new NoSuchElementException();\r\n }\r\n if (items.size() == 1) return items.remove(0);\r\n T x = items.get(0);\r\n items.set(0, items.remove(items.size()-1));\r\n shiftDown();\r\n return x;\r\n }\r\n \r\n public int size() {\r\n return items.size();\r\n }\r\n \r\n public boolean isEmpty() {\r\n return items.isEmpty();\r\n }\r\n \r\n public String toString() {\r\n return items.toString();\r\n }\r\n \r\n public T max() {\r\n return items.get(0);\r\n }\r\n public void print() {\r\n for (int i = 0; i < items.size(); i++) {\r\n System.out.print(items.get(i).toString() + \" \");\r\n }\r\n System.out.println();\r\n }\r\n}\r\n \r\nclass Codechef { \r\n\tpublic static void main (String[] args) {\r\n\t\tHeap <Integer> test = new Heap<Integer> ();\r\n\t\ttest.insert(16);\r\n\t\ttest.insert(9);\r\n\t\ttest.insert(11);\r\n\t\ttest.insert(10);\r\n\t\ttest.insert(13);\r\n\t\ttest.insert(31);\r\n\t\ttest.insert(19);\r\n\t\ttest.insert(2);\r\n\t\ttest.insert(50);\r\n\t\ttest.insert(23);\r\n\t\ttest.print();\r\n\t\t\/\/To kill some hares in the same time:\r\n\t\t\/\/- isEmpty() works;\r\n\t\t\/\/ max() and toString() too\r\n\t\t\/\/ so does delete() => shiftDown() works;\r\n\t\t\/\/ heapsort :D\r\n\t\tfor (;!test.isEmpty();) {\r\n\t\t System.out.print(test.max().toString() + \" \");\r\n\t\t test.delete();\r\n\t\t}\r\n\t}\r\n}<\/pre>\n