/*o(n)的堆化方法*/

void myjust(vector<int>& A,int i)
{
int l=i*2+1;
int r=i*2+2;
int minn=i;
if(l<A.size()&&A[l]<A[minn])
minn=l;
if(r<A.size()&&A[r]<A[minn])
minn=r;
if(minn!=i)
{
swap(A[minn],A[i]);
myjust(A,minn);
}
}

void heapify(vector<int> &A) {
int lens=A.size();
if(lens==0) return;
for(int i=lens/2;i>=0;i--)
{
myjust(A,i);
}
}

键树

class Trie {

public:

	struct TrieNode {

		bool isEnd;

		map<char, TrieNode*> myMap;

		TrieNode()

		{

			isEnd = false;

		}

	};

	TrieNode* root;

	/** Initialize your data structure here. */

	Trie() {

		root = new TrieNode();

	}

	/** Inserts a word into the trie. */

	void insert(string word) {

		TrieNode* current = root;

		for (int i = 0; i < word.length(); i++)

		{

			if (current->myMap.find(word[i]) != current->myMap.end())

			{

				current = current->myMap[word[i]];

				if (i == word.length() - 1)

					current->isEnd = true;

			}

			else

			{

				TrieNode* tmp = new TrieNode();

				tmp->isEnd = (i == word.length() - 1 ? true : false);

				current->myMap[word[i]] = tmp;

				current = tmp;

			}

		}

	}

	/** Returns if the word is in the trie. */

	bool search(string word) {

		TrieNode* current = root;

		for (int i = 0; i < word.length(); i++)

		{

			if (current->myMap.find(word[i]) != current->myMap.end())

			{

				current = current->myMap[word[i]];

			}

			else

			{

				return false;

			}

		}

		return current->isEnd == true ? true : false;

	}

	/** Returns if there is any word in the trie that starts with the given prefix. */

	bool startsWith(string prefix) {

		TrieNode* current = root;

		for (int i = 0; i < prefix.length(); i++)

		{

			if (current->myMap.find(prefix[i]) != current->myMap.end())

			{

				current = current->myMap[prefix[i]];

			}

			else

			{

				return false;

			}

		}

		return true;

	}

};

int getIdx(vector<int>& nums,int left,int right)

{

    int tmp=nums[left];

    while(left<right)

    {

        while (left<right&&nums[right]>=tmp)

            right--;

        nums[left]=nums[right];

        while (left<right&&nums[left]<tmp)

            left++;

        nums[right]=nums[left];

    }

    nums[left]=tmp;

    return left;

}

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {

    vector<int> ans;

    if(input.size()<k||k<=0||input.size()==0)

    {

        return ans;

    }

    int idx=-1;

    int left=0,right=input.size()-1;

    while (idx!=k-1)

    {

        idx=getIdx(input,left,right);

        if(idx>k-1)

        {

            right=idx-1;

        }

        else

        {

            left=idx+1;

        }

    }

    for(int i=0;i<k;i++)

    {

        ans.push_back(input[i]);

    }

    return ans;

}